素数的判断

题设：输入一个n，请你输出2-n的所有素数。

素数：大于 1 且仅能被 1 和自身整除的正整数。

这里可以使用6k±1来优化流程。

理论：所有大于3的素数都可以表示为6k±1的形式。

例如：5=6-1，11=12-1

所有整数可以表示为：

1. 6k
2. 6k-5   6k+1
3. 6k-4   6k+2
4. 6k-3   6k+3
5. 6k-2   6k+4
6. 6k-1   6k+5

当k≥0时，每一行的两个所表示的正整数集是完全相同的。

容易发现：所有正整数且无2，3因子的大于3的数，只能是6k±1的形式。

但是是6k±1形式的数，不一定是素数。例如25，他是5的平方，是合数。

这给我们的筛选给了极大的便利，因为这直接筛选掉了2/3的数据。

优化后的流程：生成候选数列：2，3和6k±1（k≥1）

然后再对这些候选数进行精细的判断。从5开始到sqrt(6k±1)判断是否是合数。

 

为什么判断到sqrt(6k±1)就行了呢？

假设6k±1是一个合数，且n=6k±1=a×b,a≤b

a≤b 两边同乘a

a×a≤a×b=n 也就是说这个小的因子不会超过sqrt(n) 也就是说判断到sqrt(n)就行了。