一个质数筛,请求分析复杂度
  • 板块学术版
  • 楼主高way
  • 当前回复9
  • 已保存回复9
  • 发布时间2020/11/27 16:14
  • 上次更新2023/11/5 07:15:23
查看原帖
一个质数筛,请求分析复杂度
117174
高way楼主2020/11/27 16:14

以下为代码

#include <iostream>
#include <math.h>
#include <time.h>
#Include <fstream>
using namespace std;
ofstream fout("prime.txt")
int a[100000000],act,len;
/*
a存储已发现的质数,
act表示需要检测的质数数量,
len表示已有质数数。*/
int test(int t){//检测素性
int i;
for(i=0;i<act;i++){
 if(t%a[i]==0)return 0;
} 
return 1;}
int main(){
 int q,b,c;
 q=5;
 a[0]=2;a[1]=3;
 fout<<2<<endl<<3<<endl;
 act=1;
 len=1;
 while(len<100000000){
  if(a[act]*a[act]>q)act++;//更新检测的素数个数
  if(test(q)==1){
   a[len+1]=q;len++;fout<<q<<endl;
  }
  q+=2;
 }
}

谢谢各位大佬

2020/11/27 16:14
加载中...