最小素数发生器C.
我必须在C中创建一个最小素数生成器（我们需要至少有两位数的最小素数）并且我不能使用表。所以我的想法是首先找到所有素数，其次是使用掩码来查找每个素数的所有子序列。数字，最后检查每个子序列是不是素数。我找不到最小素数因为我没有设置条件来检查子序列是否为素数？（我的代码没有准备好所以它可能有一些错误，但它运行）我的代码
#include #define MAXNUMB 100 int main () { int i,j,x,mask,max=1,mult,sub; for (i = 11 ; i < MAXNUMB; i += 2 ) { for (j = 3; j * j i) { int length = 0; int tmp=i; while (tmp != 0) { tmp /= 10; length++; } for (x=1;x<length*2;x++) { mask=x; mult=1; sub=0; int num=i; while ( num != 0 ) { if ( mask % 2 == 1 ) { sub += num % 10 * mult; mult *= 10; } num /= 10; mask /= 2; } printf ("%d \n",sub); } printf ("%d is minimal prime \n",i); } } } 如果MAXNUMB不是太大，那么你可以使用Sieve_of_Eratosthenes快速找到MAXNUMB之前的所有素数。 完成后，您可以通过从1到2 ^ n-1计数得到n位数的每个子序列，并使用当前计数的位模式指定当前子序列。 检查筛子中的每个子序列。
如果MAXNUMB太大，那么你可以将筛子建立到sqrt（MAXNUMB），这样当你测试一个数字是否为素数时你只需要检查它是否可以被任何素数整除，而不是检查它是否可以被任何奇数整除数。
维基百科有一个很好的伪代码算法 。 这很天真，但它确实有效。
function is_prime(n : integer) if n ≤ 1 return false else if n ≤ 3 return true else if n mod 2 = 0 or n mod 3 = 0 return false let i ← 5 while i×i ≤ n if n mod i = 0 or n mod (i + 2) = 0 return false i ← i + 6 return true
我会留下把它翻译成C给你。 我的一点是， i应该是一个比n类型更大的类型。 因此，考虑当n是最大整数时i×i ≤ n会发生什么。
当你准备好了，你可以看看我对这个问题的解决方案 。
最小素数的概念适度有趣。 我编写了以下代码来进行检查。
/* SO 33838621: Minimal Primes */ /* ** Find the minimal primes less than 100,000. ** ** A minimal prime is a prime number for which no subsequence of the digits ** that make up the number is itself prime. ** The question gives two examples: ** = 881 is prime and is a minimal prime because none of { 8, 8, 1, 88, ** 81, 81 } are prime. ** = 109 is prime but is not a minimal prime because { 1, 0, 9, 10, 9, ** 19 } includes the prime 19. ** Clearly, the single digit primes are all trivially minimal. ** ** Additional wrinkle: the code may not build up a table of primes. ** ** NB: All primes except 2 and 3 have the form 6N±1 */ /* ** There are two problems to solve: ** (1) Check for primality without using a table of primes. ** (2) Generate all subsequences of a number. ** The latter problem is somewhat harder than the former. ** The surviving solution uses recursive string manipulation. ** ** NB: Command subsequences is derived from this, and helps check ** the validity of the minimal primes. */ #include #include #include #include #include static bool is_prime(int n) { if (n < 2) return false; if (n == 2 || n == 3 || n == 5 || n == 7) return true; if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false; for (int c = 12; (c - 1) * (c - 1) <= n; c += 6) { if (n % (c - 1) == 0 || n % (c + 1) == 0) return false; } return true; } static bool has_prime_n_digit_subset(int p0, int n_digits, const char *buffer, int buflen) { //printf("-->> p0 = %5d, n = %d (%s)\n", p0, n_digits, buffer); assert(buflen >= 0 && strlen(buffer) == (size_t)buflen); for (int i = 0; i < buflen; i++) { int p1 = 10 * p0 + buffer[i] - '0'; if (n_digits > 1) { if (has_prime_n_digit_subset(p1, n_digits - 1, &buffer[i+1], buflen - i - 1)) { //printf("<<-- true\n"); return true; } } else { //printf("C %d\n", p1); if (is_prime(p1)) { //printf("<<-- p1 = %d: true\n", p1); return true; } } } //printf("<<-- false\n"); return false; } static void check_minimal_prime(int n) { assert(n > 0); if (is_prime(n)) { //printf("P %d\n", n); char buffer[20]; sprintf(buffer, "%d", n); char n_digits = strlen(buffer); for (int i = 1; i < n_digits; i++) { if (has_prime_n_digit_subset(0, i, buffer, n_digits)) return; } printf("%d\n", n); /* It's a minimal prime */ } } int main(int argc, char **argv) { int max = 100000; if (argc > 2) { fprintf(stderr, "Usage: %s [maximum]\n", argv[0]); exit(1); } else if (argc == 2) { max = atoi(argv[1]); if (max <= 0) { fprintf(stderr, "Invalid number (%d from %s)\n", max, argv[1]); exit(1); } } max /= 6; check_minimal_prime(2); check_minimal_prime(3); for (int c = 1; c < max; c++) { check_minimal_prime(6 * c - 1); check_minimal_prime(6 * c + 1); } return 0; }
生成的数字列表是：
2 3 5 7 11 19 41 61 89 409 449 499 881 991 6469 6949 9001 9049 9649 9949 60649 666649 946669 60000049 66000049 66600049
检查高达1,000,000,000时，我没有找到任何更多的最小素数。 时间安排是：
100 0m0.006s 1000 0m0.006s 10000 0m0.006s 100000 0m0.012s 1000000 0m0.129s 10000000 0m2.617s 100000000 1m8.200s 1000000000 32m34.561s