专题：素数详解

专题：素数详解 1.素数的定义

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

2.判断素数

一个整数要被判断是否是素数，需要判断n是否能被2,3，···，n-1中的一个整除。只有2,3，···，n-1都不能整除n，n才能判定为素数，而只要有一个能整除n的出现，n就可以判定为非素数。
注意：用常规方法从2到n-1一个个除的复杂度是O(n)，实际上在题目中是有点大的，由数学知识可知：只需要判定n能否被2,3，···，【sqrt(n)】整除即可判定。
代码如下：

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

如果n没有接近int 型变量的范围上届，还有更简单的写法：

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

3.求100以内的素数

#include 
#include 
using namespace std;
bool isPrime(int n) {
	if (n <= 1) return false;
	for (int i = 2;i * i <= n;i++) {
		if (n % i == 0) return false;
	}
	return true;
}
int main() {
	for (int i = 1;i < 101;i++) {
		if (isPrime(i)) {
			cout << i<<" ";
		}
	}
	return 0;
}

4.素数筛选法

const int maxn = 101;
int prime[maxn], pNum = 0;
bool p[maxn] = { 0 };
void Find_Prime() {
	for (int i = 2;i < maxn;i++) {
		if (p[i] == false) {
			prime[pNum++] = i;
			for (int j = i + i;j < maxn;j += i) {
				p[j] = true;
			}
		}
	}
}

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

#include 

const int maxn = 101;
int prime[maxn], pNum = 0;
bool p[maxn] = { 0 };
void Find_Prime() {
	for (int i = 2;i < maxn;i++) {
		if (p[i] == false) {
			prime[pNum++] = i;
			for (int j = i + i;j < maxn;j += i) {
				p[j] = true;
			}
		}
	}
}
int main() {
	Find_Prime();
	for (int i = 0;i < pNum;i++) {
		printf("%d ", prime[i]);
	}
	return 0;
}