1.简单的素数筛选法
#include<stdio.h> #include<string.h> #include<math.h> int prime(int n){ //sqrt(n)表示 //如果n在(1,sqrt(n)]的区间内没有因数，n在(sqrt(n),n)的区间中就没有因数 //sqrt(n)的平方等于n，若有其余的因数必定是一个为c,一个为d,c*d=n，c处于sqrt(n)左边,d于sqrt(n)右边 for(int i=2;i<=sqrt(n);i++){ if(!(n%i)){ return 0; } } return 1; } int main(){ int a[100010]; a[1]=0; for(int i=2;i<=100000;i++){ a[i]=prime(i); } }2.快速筛选素数
#include<stdio.h> #include<math.h> #include<string.h> int main(){ int a[100010]; //首先将数组全部赋值为1 memset(a,1,sizeof(a)); //1不是素数，赋值为0 a[1]=0; for(long long i=2;i<=100000;i++){ //合数必然是素数的整数倍 //在不包含0和1的区间中，不是合数，就是素数 if(a[i]){ for(long long j=i*i;j<=100000;j+=i){ //合数赋值为0 a[j]=0; } } } }