狂人之家吧 关注:3贴子:170
  • 2回复贴,共1

快速找质数代码

只看楼主收藏回复

//找质数精简版
#include <iostream>
#include <time.h>
#include <cmath>
#include <fstream>
#include <iomanip>
using namespace std;
unsigned long j;
long double i;
FILE * newfile;
int main()
{
//加入测试运行时间
clock_t starttime,endtime; //创建两个时间型变量,代表开始时间与结束时间
unsigned long number; //创建一个无符号长整形变量
unsigned long len;
ofstream myfile("num.txt"); //打开记录文件
streambuf * n=cout.rdbuf(myfile.rdbuf());
cin>>number; //要求用户输入一个数值,并将它赋给number变量
starttime=clock(); //程序将要进入计算,让计时器的初始值赋给开始时间
unsigned long *myarr=new unsigned long [number]; //myarr是一个指向长整型一维数组的指针
memset(myarr,0,number); //初始化所有元素为0
len=3; //计数初始化
myarr[0]=3; //初始化第一个元素是3
myarr[1]=5;
myarr[2]=7;
cout<<myarr[0]<<endl
<<myarr[1]<<endl
<<myarr[2]<<endl;
for (i=9;i<number;i+=2) //从9循环到用户给定的数值,并跳过偶数
{
for (j=0;myarr[j]<sqrt(i);++j)//在质数数组中循环
{
if (unsigned long(i)%myarr[j]==0) //如果某一数值可以被任意比它小的质数整除,分成以下两种情况
{
break; //不是素数
}
else
{
if (myarr[j+1]>sqrt(i) && unsigned long(i)%7!=0)
{
myarr[len+1]=i;
cout<<setprecision(13)<<i<<endl;
len++;
break;
}
}
}
}
delete []myarr;
endtime=clock();
long timer=endtime-starttime;
cout.rdbuf(n);
cout<<"共计算了"<<number<<"个数值"<<endl;
cout<<"共找到"<<len<<"个质数,"<<"耗时"<<timer/60000<<"分"<<timer%60<<"秒"<<endl;
system("pause");
}


1楼2016-07-21 17:40回复
    可以查看计算时长的,并输出到文件。我试验了一亿个数,共用了19分52秒


    2楼2016-07-21 17:41
    收起回复