【c++】素数

• 质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。【*】
• 知乎问题：哪个算法是判断素数的最简单算法  https://www.zhihu.com/question/19668324

Q：输入一个正整数 输出0到该范围内的素数

• 1 最基础的办法，用从2开始的每个数依次作余运算

#include<iostream>
using namespace std;

int main() {
	int input;
	int flag;
	cout << "请输出一个正整数 判断到0到该数之间的素数：";
	cin >> input;
	for (int i = 2; i < input; i++) {
		flag = 0;
		for (int j = 2; j<i ; j++) {
			if (i%j == 0) { flag = 1; break; }
		}
		if (flag == 0)cout << i << " ";
	}
	cout << endl;
}

运行结果如下

• 解析：例如输入的是10，则对1-10这10个数字分别判断是否为素数

从i=2开始， j=i=2 不执行i%j这步 直接输出2

    i=3     j=2     3%2!=0  flag=0 输出3

    i=4      j=2     4%2==0 flag=1 跳出

    i=5      j=2     5%2!=0  flag=0   

            j=3     5%3!=0  flag=0

    j=4     5%4!=0  flag=0 输出5

  同理进行此后的运算。

缺点：时间复杂度高

• 2  优化算法1：遍历N能否能被从2到sqrt(N)之间的素数整除。若不能则为素数。

#include<iostream>
#include<math.h>
using namespace std;

int main() {
	int input;
	int flag;
	cout << "请输出一个正整数 判断到0到该数之间的素数：";
	cin >> input;
	for (int i = 2; i < input; i++) {
		flag = 0;
		for (int j = 2; j<=sqrt(i) ; j++) {
			if (i%j == 0) { flag = 1; break; }
		}
		if (flag == 0)cout << i << " ";
	}
	cout << endl;
}

此时 对于每一个整数，只用测试根号下n-1次

网上也有通过在sqrt(i+0.5)或者用j*j<=i的方法来避免了根号精度误差的问题

• 埃拉托斯特尼 筛选法

算法原理： 从2开始，将每个素数的各个倍数，标记成合数

一个素数的各个倍数，是一个差为此素数本身的等差数列。

点击打开链接

算法的关键在于，以素数来测试每个待测数能否被整除。

实现如下：

#include<iostream>
#include<cmath>
using namespace std;
#define max 1000
bool arr[max];
int n;
void isprime() {
	for (int i = 2; i < n; i++)
		arr[i] = true;

	for (int i = 2; i*i < n; i++) {
		if (arr[i]) {
			for (int j = i*i; j < n; j += i)
				arr[j] = false;
		}
	}
}

int main() {
	cout << "输入一个大于2的整数：";
	cin >> n;

	isprime();
	for (int i = 2; i < n; i++) {
		if (arr[i])
			cout  <<i<< " ";
	}
	cout << endl;
}

结果如下

欧拉筛选法

埃筛会对重复对两个素数乘积的倍数重复判断

例如 埃筛第一轮确认素数2 则筛去4 6 8 12...24...

确认素数3 则筛去6 9 12 15 18 21 24..

欧拉筛选法是一边判断素数 一边进行记录，每次只筛走当前数字后一段范围的倍数。

若当前数是一个合数，则素因数肯定能在已找出来的素数中找到。

#include<iostream>
#include<cmath>
using namespace std;
#define max 1000
int n;
int primenum = 0;
bool arr[max];
int prime[max];

int main() {
	cout << "输入一个大于2的整数：";
	cin >> n;
	for (int i = 2; i < n; i++) {
		arr[i] = true;//数组全初始化为是素数
	}

	for (int i = 2; i < n; i++) {
		if (arr[i]) {//若是素数 记录入prime中
			prime[primenum++] = i;
		}
		for (int j = 0; (j < primenum)&&(i*prime[j] < n); j++) {
			arr[i*prime[j]] = false;//当前数字与小于等于它的素数逐个相乘筛倍数
			if (i%prime[j] == 0)break;//标志合数
		}
		if (arr[i]) cout << i << " ";
	}
}

结果如下

参考资料：

素数的定义 https://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

埃筛 

https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95

BruceKing 初等数学  https://bruceking.site/blog/