数学问题——素数

素数又称为质数，是指除了 1和本身之外，不能被其他数整除的一类数。应特别注意的是，1既不是素数，也不是合数。

本章将解决两个问题：1.如何判断给定的正整数 n是否是质数；2.如何在较短的时间内得到 1~n内的素数表。

一、素数的判断

只需要判定 n能否被 2，3，... ，$ \left \lfloor sqrt(n) \right \rfloor $中的一个整除，即可判断 n是否为素数。该算法的复杂度为 O(sqrt(n))。

代码如下：

1 // 判断 n 是否为素数 
2 bool isPrime(int n) {
3     if(n <= 1) return false;    // 特判
4     int sqr = (int)sqrt(n*1.0);    // 根号 n
5     for(int i=2; i<=sqr; ++i) {    // 遍历 2~根号n 
6         if(n%i == 0)    return false;s
7     } 
8     return true;
9 }

二、素数表的获取

通过上面的学习，已有办法判断单独一个数是否是素数，那么可以从 1~n进行遍历，判断每个数是否是素数，如果是素数则加入素数表。下面是完整的求解 100以内的所有素数的程序：

1 /*
 2     素数 
 3 */
 4 
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <stdlib.h>
 9 #include <time.h>
10 #include <stdbool.h> 
11 
12 // const 在 c 中不代表常量 
13 #define maxn 101    // 表长
14 int pri[maxn], pNum=0;    // prime 储存素数，pNum 储存素数个数 
15 
16 // 判断 n 是否为素数 
17 bool isPrime(int n) {
18     if(n <= 1) return false;    // 特判
19     int sqr = (int)sqrt(n*1.0);    // 根号 n
20     // c 要求先定义变量 
21     int i;
22     for(i=2; i<=sqr; ++i) {    // 遍历 2~根号n 
23         if(n%i == 0)    return false;
24     } 
25     return true;
26 } 
27 
28 // 素数表获取 
29 void findPrime() {
30     int i;
31     for(i=1; i<101; ++i) {
32         if(isPrime(i)) {
33             pri[pNum++] = i;
34         }
35     }
36 } 
37 
38 int main() {
39     findPrime();
40     int i;
41     for(i=0; i<pNum; ++i) {
42         printf("%d ", pri[i]);
43     }
44     
45     return 0;
46 }

下面介绍一个更高效的算法，埃氏筛选。算法从小到大枚举所有数，对每一个素数，筛去其所有的倍数，剩下的就都是素数。至于“筛”这个动作的实现，可以使用一个 bool型数组 p来标记，如果 a被筛掉，那么 p[a]为 true；否则，p[a]为false。在程序开始时可以初始化 p数组全为 false。

下面是完整的用素数筛法求解 100以内的所有素数的程序：

1 /*
 2     素数_埃氏筛选 
 3 */
 4 
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <stdlib.h>
 9 #include <time.h>
10 #include <stdbool.h>
11 
12 #define maxn 101
13 int pri[maxn], pNum=0;
14 bool p[maxn] = {0};    // 表示数是否被筛掉
15 
16 // 素数表的获取，埃氏筛选
17 void findPrime() {
18     int i;
19     for(i=2; i<maxn; ++i) {
20         if(!p[i]) {                // 没有被筛掉，为素数 
21             pri[pNum++] = i;
22             int j; 
23             for(j=i+i; j<maxn; j+=i) {    // 筛掉倍数 
24                 p[j] = true;
25             }
26         }
27     } 
28 } 
29 
30 int main() {
31     findPrime();
32     int i;
33     for(i=0; i<pNum; ++i) {
34         printf("%d ", pri[i]);
35     } 
36 
37     return 0;
38 }

【PAT B1013】数素数

题目：令P_i表示第i个素数。现任给两个正整数M <= N <= 10⁴，请输出P_M到P_N的所有素数。

思路：把素数表打至第 N个素数，然后按格式输出即可。

下面是完整的程序：

1 /*
 2     【PAT B1013】数素数
 3 */
 4 
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <stdlib.h>
 9 #include <time.h>
10 #include <stdbool.h>
11 
12 #define maxn 1000001
13 int pri[maxn], pNum=0;
14 bool p[maxn] = {0};    // 表示数是否被筛掉
15 
16 // 素数表的获取，埃氏筛选
17 void findPrime(int n) {
18     int i;
19     for(i=2; i<maxn; ++i) {
20         if(!p[i]) {                // 没有被筛掉，为素数 
21             pri[pNum++] = i;
22             if(pNum >= n) break;    // 只把素数表打至第 N 个素数 
23             int j; 
24             for(j=i+i; j<maxn; j+=i) {    // 筛掉倍数 
25                 p[j] = true;
26             }
27         }
28     } 
29 } 
30 
31 int main() {
32     int m, n;
33     scanf("%d%d", &m, &n);    // 输入 m,n
34     findPrime(n);            // 生成素数表
35     int i, cnt=1;
36     for(i=m; i<=n; ++i) {
37         printf("%d", pri[i-1]);    // 数组下标从 0 开始
38         if((cnt++)%10 && i<n) printf(" ");
39         else printf("\n");        // 每10个数字占1行 
40     } 
41 
42     return 0;
43 }