算法笔记 素数

素数又称为质数，是指除了 1 和本身以外，不能被其它数整除的一类数。

需要注意： 1 不是素数

一、素数的判断

1.简单思路

只需要判断 n 能够被 2, 3, ···, n - 1 整除，就可以判断 n 是否为素数。该算法的时间复杂度为 o(n) 。

2.更快思路

若 2 ~ n - 1 中存在 n 的约数 k ，有 n % k == 0 ，假设 n / k = m ，则一定有 n % m == 0 。即若 n 有约数，则其约数一定是成对出现的，且一个 >= sqrt(n) ，另一个 <= sqrt(n) ，其中 sqtr(n) 为根号 n 。

因此，只需要判断 n 能否被 2, 3, ···, sqrt(n) 整除，即可判断 n 是否为素数。该算法的时间复杂度为 o(sqrt(n)) 。

代码如下：

1
2
3
4
5
6
7
8
bool isPrime(int n){
	int i;
	if (n <= 1)    return false;
	int sqr = (int)sqrt(1.0 * n);
	for (i = 2; i <= sqr; i++)
		if (n % i == 0)    return false;
	return true;
}

sqrt 的作用为给浮点数开根号，需要添加 math.h 头文件，由于 sqrt 的参数要求为浮点数，因此在 n 前面乘以 1.0 使其成为浮点型。

若 n 的数字较小，有简单写法：

1
2
3
4
5
6
7
bool isPrime(int n){
	int i;
	if (n <= 1)    return false;
	for (i = 2; i * i <= n; i++)
		if (n % i == 0)    return false;
	return true;		
}

二、素数表的获取

1.简单思路

从 1 ~ n 进行枚举，判断每一个数是否为素数，如果是素数则加入素数表。这种方法枚举部分的复杂度为 o(n) ，而对每个数字判断素数的复杂度为 o(n0.5) ，因此总复杂度为 o(n1.5) 。这个复杂度对于 n 不超过 105 的大小是没有问题的。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int maxn = 101;
int prime[maxn];  //存放素数
int pnum = 0;  //素数个数及数组下标
bool p[maxn] = {0};  //p[i] == true 表示i是素数

bool isprime(int n);  //判断是否为素数

void FindPrime(){
	int i;
	for (i = 1; i < maxn; i++)
		if (isPrime(i) == true){
			prime[pnum++] = i;
			p[i] = true;
		}
}

2.埃式筛法

素数筛法的关键在于“筛”，算法从小到大枚举所有数，对每一个素数，筛去它的所有倍数，剩下的就都是素数了。

例如：

求 1 ~ 15 中的所有素数。

由上述例子可以发现，由小到大进行遍历，当到达某个数时，如果它还没有被筛掉，说明它是素数。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int maxn = 101;
int prime[maxn];  //存放素数
int pnum = 0;  //素数个数及数组下标
bool p[maxn] = {0};  //p[i]为假是素数，为真被筛掉

void FindPrime(){
	int i, j;
	for (i = 2; i < maxn; i++){
		if (p[i] == flase){  //如果是素数
			prime[pnum++] = i;
			for (j = 2 * i; j < maxn; j += i)    p[j] = true;  //筛掉倍数
		}
	}
}

这个算法的时间复杂度为 o(nloglogn) ，是更加高效的算法。

【PAT B1013】数素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

bool isPrime(int n){
	int i;
	if (n <= 1)    return false;
	int sqr = (int)sqrt(1.0 * n);
	for (i = 2; i <= sqr; i++)
		if (n % i == 0)    return false;
	return true;
}

int main(){
    int i, j;
    int m, n;
    scanf("%d %d", &m, &n);
    int *prime = (int*)malloc(sizeof(int) * n);
    for (i = 1, j = 0; j < n; i++){
        if (isPrime(i))    prime[j++] = i;
    }
    for (i = m - 1, j = 0; i < n; i++, j++){
        if (j % 10 == 0 && j != 0)    printf("\n");
        else if (j != 0)    printf(" ");
        printf("%d", prime[i]);
    }    
}

​

参考

  • 算法笔记