求质数算法C++_质数怎么求c++

点击打开参考 点击打开参考

#include <iostream>
#includ <cmath>
using namespace std;
 
//求小于m的所有素数
void prime_number(int m){
	int i,j,k;
	bool* Num;
	Num = new bool[m];
	for(int i=0;i<m;i++){
		if(i==0)
			Num[i] = false;
		else
			Num[i] = true;
	}
	k=1;
	while(k<m){
		for(i=k; i<m; i++){
			if(Num[i]){
				for(j=i+1; j<m; j++){
					if((j+1)%(i+1) == 0)
						Num[j] = false;
				}
				break;
			}
		}
		k = i+1;
	}
	for(i=0; i<m; i++){
		if(Num[i])
			cout<<i+1<<endl;
	}
	delete []Num;
}
 
//从小到大求n个素数
//素数定理可以给出第n个素数p(n)的渐近估计：p(n)约等于nlogn.实际上p(n)一般不会大于(1+15%)*nlogn.所以方案二根据这个思路先确定一个p(n)(肯定包含n个素数)，再用筛选法排除p(n)的所有合数，最后输出n个素数即可
void prime_number(int m, int n){
	int i,j,k,count = 0;
	bool* Num;
	Num = new bool[m];
	for(i=0;i<m;i++){
		if(i==0)
			Num[i] = false;
		else
			Num[i] = true;
	}
	k = 1;
	while(k<m){
		for(i=k; i<m; i++){
			if(Num[i]){
				for(j=i+1;j<m;j++){
					if((j+1)%(i+1) == 0)
						Num[j] = false;
				}
				break;
			}
		}
		k = i+1;
	}
	for(i = 0;i<m;i++){
		if(Num[i]){
			cout<<i+1<<endl;
			count++;
		}
		if(count == n)
			break;
	}
	delete []Num;
}
 
int main(){
	int m;
	cout<<"please input a number larger than 2 "<<endl;
	cin >> m;
	prime_number(m);
	int n = m*log(m)*1.5;
	prime_number(n,m);
	return 0;
}