素数的定义：只能被1和它自己整除的自然数称为素数，特别规定1不属于素数。
根据素数的定义，很明显，如果一个数是素数<==>它的因子只包含1和它本身。因此可以根据判别某个数的因子的方法来判断其是否是素数。
01 |
int isprime(int n) |
02 |
{ |
03 |
int i; |
04 |
for(i=2;i<=(int)sqrt((double)n);i++) |
05 |
{ |
06 |
if(n%i==0) //如果n存在其它因子,则必定不是素数 |
07 |
{ |
08 |
return 0; |
09 |
} |
10 |
} |
11 |
return 1; |
12 |
} |
但是如果要求求出1000000以内的所有素数，上面的方法效率就很低，因此通常采用筛选法去求素数。筛选法：对于一个数n，如果是素数，那么2*n，3*n，4*n，必定不是素数。
01 |
bool isprime[1000001]; |
02 |
int prime[80000]; |
03 |
int num=0; |
04 |
05 |
void getPrime() //用筛选法求算素数 |
06 |
{ |
07 |
int i,j; |
08 |
for(i=0;i<1000001;i++) |
09 |
{ |
10 |
isprime[i]=true; |
11 |
} |
12 |
for(i=2;i<=1000;i++) //如果isprime[i]==true,即i是素数，那么i，2*i，3*i必定不是素数 |
13 |
{ |
14 |
for(j=i+i;j<=1000000;j+=i) |
15 |
{ |
16 |
if(isprime[i]==true) |
17 |
isprime[j]=false; |
18 |
} |
19 |
} |
20 |
for(i=2;i<1000001;i++) |
21 |
{ |
22 |
if(isprime[i]==true) |
23 |
{ |
24 |
prime[num++]=i; |
25 |
} |
26 |
} |
27 |
} |
筛选法求素数有一个很通用的算法，就是在遍例该集合时，比方检验一个数N是否素数，用N除以2-N的开方，只要有一个能整除，就说明N不是素数。另外这道题要求用数组来计算。
所谓"筛选法"指的是"埃拉托色尼(Eratosthenes)筛法"。他是古希腊的著名数学家。他采取的方法是，在一张纸上写上1到100全部整数，然后逐个判断它们是否是素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。
具体做法如下：
- 先将1挖掉(因为1不是素数)。
- 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
- 用3去除它后面的各数，把3的倍数挖掉。
- 分别用4、5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如找1～50的素数，要一直进行到除数为47为止（事实上，可以简化，如果需要找1～n范围内素数表，只需进行到除数为n^2(根号n)，取其整数即可。例如对1～50，只需进行到将50^2作为除数即可。）
如上算法可表示为：
- 挖去1;
- 用刚才被挖去的数的下一个数p去除p后面各数，把p的倍数挖掉;
- 检查p是否小于n^2的整数部分（如果n=1000, 则检查p<31?），如果是，则返回(2)继续执行，否则就结束;
- 纸上剩下的数就是素数。
01 |
#include <stdio.h> |
02 |
#include <math.h> |
03 |
int main(void) |
04 |
{ |
05 |
int i; |
06 |
int j; |
07 |
int a[101]; // 为直观表示，各元素与下标对应，0号元素不用 |
08 |
for (i = 1; i <= 100; i++) // 数组各元素赋值 |
09 |
a[i] = i; |
10 |
for (i = 2; i < sqrt(100); i++) // 外循环使i作为除数 |
11 |
for (j = i + 1; j <= 100; j++) // 内循环检测除数i之后的数是否为i的倍数 |
12 |
{ |
13 |
if (a[i] != 0 && a[j] != 0) // 排除0值元素 |
14 |
if (a[j] % a[i] == 0) |
15 |
a[j] = 0; // i后数若为i的倍数，刚将其置0(挖去) |
16 |
} |
17 |
int n = 0; // 对输出素数计数, 以控制换行显示 |
18 |
for (i = 2; i <= 100; i++) // 输出素数 |
19 |
{ |
20 |
if (a[i] != 0) |
21 |
{ |
22 |
printf("%-5d", a[i]); // 输出数组中非0元素(未挖去的数) |
23 |
n++; |
24 |
} |
25 |
if (n == 10) |
26 |
{ |
27 |
printf("\n"); // 每行10个输出 |
28 |
n = 0; |
29 |
} |
30 |
} |
31 |
printf("\n"); |
32 |
return 0; |
33 |
} |