一、根据定义
设判断n是否为素数。用2~(sqrt(n)+1)的数来除以要判断的数。
二、定义的改进
用2~sqrt(n)+1之内的素数来除以要判断的数。
我测了下不同范围内素数的比例，从小到大。下面列出一些数据，来增加些感性的认识。
//先是小范围的
1000范围内,素数所占比例为0.179000
2000范围内,素数所占比例为0.158500
3000范围内,素数所占比例为0.148667
11000范围内,素数所占比例为0.123818
12000范围内,素数所占比例为0.122250
13000范围内,素数所占比例为0.121308
47000范围内,素数所占比例为0.104213
48000范围内,素数所占比例为0.104021
49000范围内,素数所占比例为0.103714
68000范围内,素数所占比例为0.100426
69000范围内,素数所占比例为0.100130
70000范围内,素数所占比例为0.099871
//接着是大范围的
160000范围内,素数所占比例为0.092256
460000范围内,素数所占比例为0.083872
810000范围内,素数所占比例为0.080046
1110000范围内,素数所占比例为0.078042
3060000范围内,素数所占比例为0.072243
4710000范围内,素数所占比例为0.070051
5010000范围内,素数所占比例为0.069757
6960000范围内,素数所占比例为0.068173
可见这个改进还是不错的。 然而更高效的见下面的筛选法。
三、筛选法
这里的高效一部分体现在少了除法，还有一部分是因为不像之前的试除，而是类似直接构造(非素数)。
（ps.标记为1的不是素数）
1、第一种 (同样，经过实验，表明这个方法比之前的第二种方法要快很多)
prime1[0] = prime1[1] = 1; for(i = 2; i < n; i++) { for(j = 2; i*j <= n && j <= i; j++) { prime1[i*j] = 1; } }
2、第二种
prime2[0] = prime2[1] = 1; for(i = 2; i < n; i++) { if(!prime2[i]){ for(j = 2; i*j <= n; j++) { prime2[i*j]=1; } } }
两种方法依据的原理不同。
第一种：是通过所有两个因子的组合来得到合数。
第二种：内层一次循环排除掉一个素数的所有倍数。该方法能方便地从小到大选出素数。
3、第三种
由于所有大于等于5的素数都能表述成6N±1的形式。所以可以先通过这个式子筛选一遍。再对剩下的数进行进一步筛选。
（注意：并不是说符合6N±1形式的数就是素数）
