本文共 1968 字,大约阅读时间需要 6 分钟。
素数的定义:只能被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全部整数,然后逐个判断它们是否是素数,找出一个非素数,就把它挖掉,最后剩下的就是素数。
具体做法如下:
如上算法可表示为:
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 | } |
转载地址:http://klzqi.baihongyu.com/