算法笔记5.4 数学问题->素数 普通做法 埃式筛法

1.判断素数

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

#include<iostream>		 
#include<cmath>
using namespace std;

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;
}

int main(){
	int index=0;
	for(int i=2;i<=100;i++){
		if(isPrime(i)){
			cout<<i<<"\t";
			index++;
			if(index%5==0&&index!=0) cout<<endl;
		}
	}
	cout<<endl;
	return 0;
}

 

 

2.求素数表

#include<iostream>		 
#include<cmath>
using namespace std;
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;
}
int prime[101],pNum=0;
bool p[101]={0};
const int N=100;
void Find_Prime(){
	for(int i=1;i<=N;i++){
		if(isPrime(i)){
			prime[pNum++]=i;
			p[i]=true;
		}
	}
}

int main(){
	Find_Prime();
	for(int i=0;i<pNum;i++){
		printf("%d ", prime[i]);
	}
	cout<<endl;
	return 0;
}

 

3.埃式筛法  求素数

#include<iostream>		 
using namespace std;
const int N=100;
int prime[N],pNum=0;
bool p[N]={0};//素数为false 0

void Find_Prime(){
	for(int i=2;i<=N;i++){
		if(p[i]==false){
			prime[pNum++]=i;
			for(int j=i+i;j<=N;j+=i){//注意是j+=i  不是j++
				p[j]=true;
			}
		}
	}
}

int main(){
	Find_Prime();
	for(int i=0;i<pNum;i++){
		cout<<prime[i]<<" ";
	}
	cout<<endl;
	return 0;
}