算法笔记-数学问题-素数

素数判别

素数表

代码

#include <iostream>
#include <cmath>
#include <cstring> 
#include <algorithm>
using namespace std;
const int maxn = 101;
/*----- 素数判别 -----*/
bool isPrime(int a) {
	if(a<=1)return false; //0 1 既不是素数也不是合数 
	//for(int i=2;i*i<=a;i++)// 该写法i*i可能导致溢出
	for(int i=2; i<=sqrt(a); i++) {
		if(a%i==0)return false;
	}
	return true;
}
/*---- 常规素数表O(n^(3/2)) -----*/
int prime[maxn],p[maxn],pnum=0;
void find_prime() {
	for(int i=1; i<maxn; i++) {
		if(isPrime(i)){
			prime[pnum++]=i;
			printf("%d ",i);
			p[i]=1;
		}
	}
}
/*----- 埃式筛法素数表O(nloglogn) -----*/
void find_prime_a(){
	for(int i=2;i<maxn;i++){
		if(p[i]==0){
			prime[pnum++]=i;
			printf("%d ",i);
			for(int j=i+i;j<maxn;j+=i){
				p[j]=1;
			}
		}
	}
}
int main(int argc, char * argv[]) {
	int n;
//	scanf("%d",&n);
//	printf("%s
",isPrime(n)?"yes":"no");
	find_prime();
	printf("
");
	fill(prime,prime+maxn,0);
	fill(p, p+maxn, 0);
	pnum=0;
	find_prime_a();
	return 0;
}