本文提供两种快速判断素数的方法。

方法一

判断一个数n是否为素数，一般的做法是遍历不超过sqrt(n)的所有数，看是否都不能整除n，只要有一个能整除，就不是素数。

但这里循环遍历的步长为1（即遍历时自增1），另一种做法可以将步长改进到6，每次判断两个数，具体如下。

1. 先将n模 6 运算取得余数r。只有余数为1或5才可能是素数，其他都有因数2或3。

后续仅需要判断形如6x+1或6x+5的n。

2. 与一般做法一样，遍历不超过sqrt(n)去判断，但是只需要判断6x+1或6x+5的数，因为含因数2或3的数一定不能整除n。

代码如下：

int is_prime(unsigned long long n){unsigned long long r;unsigned long long i;switch (n){case 0:case 1:case 4:return 0;case 2:case 3:case 5:return 1;default:r = n % 6;if (r != 1 && r != 5) return 0;for (i = 5; i * i <= n; i += 6){if (n % i == 0 || (n % (i + 2)) == 0)return 0;}return 1;}}

方法二

在方法一的基础上，我们可以提前计算出一定范围的结果保存在变量中，判断时直接查找结果。为了节约空间，仅保存形如6x+1或6x+5的n的结果。

方法二与方法一的用时相差一个数量级，但需要空间。

1. 构造素数表prime_table.c

每个字节8位，可以记录8个结果。等价于每24个数需要1个字节。（例如n从0到24，其中需要保存结果的只有8个数）

构造的函数如下：

int make_prime_table(unsigned long long max_n){FILE*fp;unsigned long long p;unsigned long long i;unsigned char v = 0x00;unsigned char bit; /* 0, 1, 2, ..., 7 */unsigned long long write_bytes = 0;if ((fp = fopen("prime_table.c", "w+")) == NULL)return -1;fprintf(fp, "#define PRIME_TABLE_SIZE %lld\n", max_n);fprintf(fp, "unsigned char g_prime_table[] = \n{");for (i = 0; i < max_n + 8; i++){p = i % 6;if (p != 1 && p != 5)continue;bit = (i % 24) / 3;v |= (((unsigned char)is_prime(i)) << bit);if (bit == 7){if (write_bytes % 8 == 0)fprintf(fp, "\n ");fprintf(fp, "0x%02x", v);fprintf(fp, ", ");v = 0x00;write_bytes++;}}fprintf(fp, "\n};\n");fclose(fp);return 0;}

例如，保存1000000以内的结果，prime_table.c如下，需要大约41KB：

2. 代码中使用

素数表是有范围的，如果超过这个范围则调用通用的is_prime。

int is_prime_fast(unsigned long long n){unsigned long long r;if (n > PRIME_TABLE_SIZE)return is_prime(n);switch (n){case 0:case 1:case 4:return FALSE;case 2:case 3:case 5:return TRUE;default:r = n % 6;if (r != 1 && r != 5)return 0;return (g_prime_table[n / 24] & (1 << ((n % 24) / 3))) > 0;}}

测例

仅以10000以内的数测试正确性。

void test_prime(){int i;int ct = 0;/* 10000以内共1229个素数 */for (i = 0; i <= 10000; i++){if (is_prime(i))ct++;}assert(ct == 1229);for (i = 0; i <= 10000; i++){assert(is_prime(i) == is_prime_fast(i));}}