最近在学C语言，在MOOC上看到翁恺老师讲的《程序设计入门——C语言》，学到老师讲到怎么用C语言测试一个数是否为整数的时候，突然想到，既然可以测试怎么一个数是否为整数，那么肯定能够找出一定范围内的数是否为整数了。
于是想了想，用了如下代码，可以简单的实现这个功能，代码如下：
#include <stdio.h>

int main(){
	int number;
	int i,j,flag=1;

	scanf("%d",&number);
	for(i=2; i<number; i++){
		for(j=2; j<i; j++){
			if(i%j==0){
				flag=0;
				break;
			}
		}
		if(flag!=0&&j==i){
			printf("%d ",i);
		}
		flag=1;
	}
	printf("\n");
	return 0;
}

质数的定义：指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数(百度百科)
自然数的定义：指用以计量事物的件数或表示事物次序的数。即用数码0，1，2，3，4……所表示的数。自然数由0开始，一个接一个，组成一个无穷的集体。自然数有有序性，无限性。分为偶数和奇数，合数和质数等(百度百科)
问题：怎么找出n(n为大于2的自然数)内的全部质数？
我们已知大于2的偶数自然数均为合数，大于2的奇数自然数却由质数和合数组成。那么，如果我们把奇数中的合数全部去掉(合数有质数相乘得到的，如：10=2*5)，奇数中的剩余部分便全是质数了，最后添加一个2便是最终结果。举例说明：
现求100以内的全部质数，将[3,100]区间的数据分为奇数和偶数，偶数部分全为合数，奇数部分有3，5，7，9，11，13，15，17，19，21，23，25，27，29，31，33，35，37，39，41，43，45，47，49，51，53，55，57，59，61，63，65，67，69，71，73，75，77，79，81，83，85，87，89，91，93，95，97，99。(以下的数字都是此数据中的数)
第一个数字是3(质数)，我们先除去range(3*2,101,2*3)的合数(因为奇数*偶数=偶数，奇数+偶数=奇数，偶数已被我们剔除，所以乘奇数倍),得到的结果有3，5，7，11，13，17，19，23，25，29，31，35，37，41，43，47，49，53，55，59，61，65，67，71，73，77，79，83，85，89，91，95，97
第二个数字是5(质数)，再除去range(5**2,101,2*5)。得到的结果有3，5，7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，61，67，71，73，77，79，83，89，91，97
第三个数字是7(质数)，再出去range(7**2,101,2*7)，得到的结果有3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97
第四个数字是9(合数)，过
第五个数字是11(质数)，但是11**2>100,则第五个数字后都不用管，再第三步的结果中添加2变为100内的全部质数。
而大于2的全部合数是：range(4,101,2),range(9,101,6),range(25,101,10),range(49,101,14)
以下是python提取质数的代码过程(返回的集合，i5处理器，10000000内的全部质数耗时约2.3s)：
from itertools import chain
def prime_set3(a):
b=[]  # 存放合数
for i in range(3, int(a**0.5)+1, 2):
number = 0
for n in range(3, i, 2):
if i % n == 0 and i > n:
number = 1
break
if number == 1:
continue
b.append(range(i**2, a+1, 2*i))
aa = set(chain([2],range(3, a+1, 2)))
bb = set(chain(*b))
prime = aa - bb
return prime
以下是上述代码的雏形：
from itertools import chain
def prime_set(a):
b=[]
for i in range(2,int(a**0.5)+1):
b.append((range(i**2,a+1,i)))
sa=set(range(2,a+1))
sb=set(chain(*b))
prime=sa-sb
return prime

之前在某次interview中被老外问到如何用SQL找出列上的质数和完全数的问题；我当时已经多年没有写过这种考算法和SQL技巧(纯粹的技巧)的语句了，乍遇此问题倒是有些棘手。现在录以记之，供人参考.
SQL> create table numbers(NO int) ;
表已创建。
SQL> insert into numbers  select rownum  from dba_objects;
已创建71937行。
SQL> commit;
提交完成。
SELECT X.NO as Primes  /*查找质数(find prime number)*/
FROM Numbers N
CROSS JOIN Numbers X
WHERE mod(X.NO, N.NO) != 0
AND N.NO < X.NO
GROUP BY X.NO
HAVING(X.NO - Count(*)) = 2;
PRIMES
---------
4931
4919
4909
4903
4889
4877
4871
4861
4831
4817
4813 ................
SELECT X.no as Perfect /*查找完全数,find perfect nober*/
FROM numbers N
CROSS JOIN numbers X
WHERE mod(X.no, N.no) = 0
and X.no > 1
AND N.no < X.no
AND N.no > 0
GROUP BY X.no
HAVING SUM(N.no) = X.no;
PERFECT
----------
6
28
496
......................
附:
select ltrim(sys_connect_by_path(rownum || '*' || lv || '=' ||  /* SQL_99乘法口诀表*/
rpad(rownum * lv, 2),
'  '))
from (select level lv from dual connect by level < 10)
where lv = 1
connect by lv + 1 = prior lv;
1*1=1
2*2=4   2*1=2
3*3=9   3*2=6   3*1=3
4*4=16  4*3=12  4*2=8   4*1=4
5*5=25  5*4=20  5*3=15  5*2=10  5*1=5
6*6=36  6*5=30  6*4=24  6*3=18  6*2=12  6*1=6
7*7=49  7*6=42  7*5=35  7*4=28  7*3=21  7*2=14  7*1=7
8*8=64  8*7=56  8*6=48  8*5=40  8*4=32  8*3=24  8*2=16  8*1=8
9*9=81  9*8=72  9*7=63  9*6=54  9*5=45  9*4=36  9*3=27  9*2=18  9*1=9
with a as
(select distinct round(a.x + b.x) x, round(a.y + b.y) y
from (select (sum(x) over(order by n)) x,
round(sum(y) over(order by n)) y
from (select n,
cos(n / 30 * 3.1415926) * 2 x,
sin(n / 30 * 3.1415926) y
from (select rownum - 1 n
from all_objects
where rownum <= 30 + 30))) a,
(select n,
(sum(x) over(order by n)) x,
round(sum(y) over(order by n)) y
from (select n,
cos(m / 3 * 3.1415926) * 2 * 15 x,
sin(m / 3 * 3.1415926) * 15 y
from (select case
when rownum <= 2 then
3
when rownum = 3 then
-2
else
-6
end m,
rownum - 1 n
from all_objects
where rownum <= 5))) b)
select replace (sys_connect_by_path(point, '/'), '/', null) star  /*SQL 绘制奥运五环*/
from (select b.y, b.x, decode(a.x, null, ' ', '*') point
from a,
(select *
from (select rownum - 1 + (select min(x) from a) x
from all_objects
where rownum <= (select max(x) - min(x) + 1 from a)),
(select rownum - 1 + (select min(y) from a) y
from all_objects
where rownum <= (select max(y) - min(y) + 1 from a))) b
where a.x(+) = b.x
and a.y(+) = b.y)
where x = (select max(x) from a)
start with x = (select min(x) from a)
connect by y = prior y and x = prior x + 1;
with a as                                             /*sql 绘制五角星*/
(select distinct round(sum(x) over(order by n)) x,
round(sum(y) over(order by n)) y
from (select n,
cos(trunc(n / 20) * (1 - 1 / 5) * 3.1415926) * 2 x,
sin(trunc(n / 20) * (1 - 1 / 5) * 3.1415926) y
from (select rownum - 1 n from all_objects where rownum <= 20 * 5)))
select replace (sys_connect_by_path(point, '/'), '/', null) star
from (select b.y, b.x, decode(a.x, null, ' ', '*') point
from a,
(select *
from (select rownum - 1 + (select min(x) from a) x
from all_objects
where rownum <= (select max(x) - min(x) + 1 from a)),
(select rownum - 1 + (select min(y) from a) y
from all_objects
where rownum <= (select max(y) - min(y) + 1 from a))) b
where a.x(+) = b.x
and a.y(+) = b.y)
where x = (select max(x) from a)
start with x = (select min(x) from a)
connect by y = prior y and x = prior x + 1;
SELECT LPAD(MONTH, 20 - (20 - LENGTH(MONTH)) / 2) MONTH,      /*sql绘制年历*/
"Sun",
"Mon",
"Tue",
"Wed",
"Thu",
"Fri",
"Sat"
FROM (SELECT TO_CHAR(dt, 'fmMonthfm YYYY') MONTH,
TO_CHAR(dt + 1, 'iw') week,
MAX(DECODE(TO_CHAR(dt, 'd'),
'1',
LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Sun",
MAX(DECODE(TO_CHAR(dt, 'd'),
'2',
LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Mon",
MAX(DECODE(TO_CHAR(dt, 'd'),
'3',
LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Tue",
MAX(DECODE(TO_CHAR(dt, 'd'),
'4',
LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Wed",
MAX(DECODE(TO_CHAR(dt, 'd'),
'5',
LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Thu",
MAX(DECODE(TO_CHAR(dt, 'd'),
'6',
LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Fri",
MAX(DECODE(TO_CHAR(dt, 'd'),
'7',
LPAD(TO_CHAR(dt, 'fmdd'), 2))) "Sat"
FROM (SELECT TRUNC(SYSDATE, 'y') - 1 + ROWNUM dt
FROM all_objects
WHERE ROWNUM <= ADD_MONTHS(TRUNC(SYSDATE, 'y'), 12) -
TRUNC(SYSDATE, 'y'))
GROUP BY TO_CHAR(dt, 'fmMonthfm YYYY'), TO_CHAR(dt + 1, 'iw'))
ORDER BY TO_DATE(MONTH, 'Month YYYY'), TO_NUMBER(week);
MONTHSunMonTueWedThuFriSat
1     1月 2010 3 4 5 6 7 8 9
2     1月 201010111213141516

给出一个自然数表(1,2,…,n),要求尽可能快的找出其中的质数,应该怎么做?

有两种思路:一种是遍历,一个个找质数,一种是去掉所有的合数.那么选择哪一种呢?
不管怎样,先来看看如何判定质数或者合数.
质数和合数的判定
质数和合数的定义在这不多讲.为判断是质数还是合数,最经典的方案就是遍历小于该数的所有整数(除了1),如果出现整除,那就不是.

就像这样:
while(i=2;i<N;i++)
{
	if(N%i==0)
	{
		return FALSE;
	}
}
return TRUE;

但这样需要扫描N-1次,对于大数而言要花相当多的时间,显然不是优解.那么在这里引入一个定理:

${theorem: }\\
\forall x\in\mathbb{z}且\ x是合数\\ \exists 1\le a\leq \sqrt{x}
\\使得 a|x$

对该定理用反证法证明:

${proof:}\\
for 合数x,\\
\exists 整数对(a,b),a\dot b=x.(a!=0 and b!=0)\\
if a&lt; \sqrt{x}\ and\ b&lt; \sqrt{x}\\
\rightarrow a\dot b &lt; x\\
\therefore 原假设不成立.\\
Q.E.D$

所以现在提出第一个改进:

只用扫描到$\sqrt{x}$即可判断是否为质数.
筛法
结合上一部分,下面提出一个在自然数表中找出质数表的一个改进方法:

在$\sqrt{x}$范围内找出质数;
清除这些质数的整数倍;
完成.

$清除所有质数的整数倍\iff 清除所有合数$

二者是等价的吗?

下面是解释:

自然的,是一个整数的整数倍的数一定是合数.所以若清除了所有的合数必然清除所有质数的整数倍.由此必要性得证.

下面是充分性:

先引入一个定理:

${theorem:}\\
	\forall x \in\mathbb{N+}\\
	x=\prod_{i=1}^{n}\ a_i,\\
	a_i\in\mathbb{N+}且a_i是质数$

下面是证明:

${proof:}
	对于质数a,可分解为1\dot a,成立.\\
	对于合数b,一定可以分解为\\ \prod_{i=1}^{n}\ m_i,m_i\in\mathbb{N+}\\
	对于m_i,若为质数,则分解停止.\\若为合数,则按照上一条,可以分解为 \prod_{i=1}^{n}\ m&#x27;_i,m&#x27;_i\in\mathbb{N+}\\
	以上过程均成立直到m^{k}_i均为质数.$

于是

$\forall a\ is\ 合数\\
	\exists m\ is\ 质数\\
	m|a\\$

充分性得证.
那么:

按照这个方法进行质数的筛选,有:
for(a=1;a<=sqrt(x);a++)
{
	if(isPrime_number(a)==1)
	{
		for(b=2;ab<=x;b++)
		{
			remove(ab);
		}
	}
	else
	{
		/*怎么会有else?*/
	}
}		

就是这样了.