我的求素数的程序，大家看看是不是最快的？还能不能优化？
#include <iostream>#include <math.h>using namespace std;int get_prime(int n)//求第n个素数{ int *p_r = new int[n]; int count = 1; p_r[0] = 2; p_r[1] = 3; for(int i=3; count!=n; i+=2) { int sqrt_i = sqrt(i); for(int j=1; sqrt_i>=p_r[j] && i%p_r[j]!=0; ++j); if(sqrt_i<p_r[j]) { p_r[count++] = i; } } return p_r[count-1];}int main(){ cout<<get_prime(10000000)<<endl; //第一千万个素数：179424673 return 0;}#include <iostream>#include <cmath>#include <cstring>using namespace std;/*********************************/* gcd(int a,int b)* 原名：欧几里得算法* 辗转相除法求最大公约数* 无所谓a,b大小次序./*********************************/int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b);}/*********************************/* lcm(int a,int b)* 求最小公倍数* 无所谓a,b大小次序./*********************************/int lcm(int a,int b){ return a/gcd(a,b)*b; //mark:计算顺序防止乘法溢出}/*********************************/* int prime(int n)* 筛法构造2....n的素数表* O(nlgn)/*********************************/const int MAXSIZE=10000000;int p[MAXSIZE];int vis[MAXSIZE];int prime(int n){ int m=sqrt(n+0.5); int c=0; memset(vis,0,sizeof(vis)); for(int i=2;i<=m;++i) { if(!vis[i]) { p[c++]=i; } for(int j=i*i;j<=n;j+=i) { vis[j]=1; } } for(int k=m+1;k<=n;++k) { if(!vis[k]) { p[c++]=k; } } return c;}/******************************************/* 调用bool result(int a,int b,int c,int &x,int &y);* gcd1(int a,int b,int &d,int &x,int &y)* 扩展欧几里得算法* 解整系数线性方程:ax+by=c* d为最大公约数,x,y为解./*******************************************/void gcd1(int a,int b,int &d,int &x,int &y){ if(!b) { d=a; x=1; y=0; } else { gcd1(b,a%b,d,y,x); y-=x*(a/b); }}bool result(int a,int b,int c,int &x,int &y){ int d; gcd1(a,b,d,x,y); if(c%d==0) { x=x*c/d; y=y*c/d; return true; } else { return false; }}/******************************************/* 模运算公式：* (a+b)mod n= ((a mod n)+ (b mod n)) mod n* (a-b)mod n= ((a mod n)-(b mod n)+ n) mod n* a*b mod n= ( (a mod n) *(b mod n) ) mod n* a*b特殊,(a mod n) *(b mod n) 可能溢出,* 用long long 保存中间计算过程, mod n后转回int* 感觉其他两种也不是说不可能溢出,万一n很大，a,b也大* 中间的计算过程依旧会溢出，所以最好都用long long* 保存中间运算的值，运算结束(int)转化回去/*******************************************//*********************************/*大整数取模运算,输入正整数 n ,m*输出n mod m, 其中n<=10e100, m<=10e9(m在int范围内)*n太大,用字符串存储,m用int存储*例如：n=1234, 可以分解:*1234=((((0*10)+1)*10+2)*10+3)*10+4 mod n*由于只有*,+运算，可以将mod放进去/*********************************/char input[200];int bigMod(char *n,int m){ int len=strlen(n); int mod=0; for(int i=0;i<len;++i) { mod=(int)(((long long )mod*10+n[i]-'0') % m); } return mod;}/*********************************/*幂取模*输入正整数a,n,m,求aEn mod m*a,n,m <=10e9*0(n)算法，O(lgn)算法/*********************************/int nPowMod(int a,int n,int m){ int ans=1; for(int i=0;i<n;++i) { ans=(int)((long long )ans*a%m); } return ans;}int nlgnPowMod(int a,int n,int m){ if(n==1) { return a%m; } else { int ret=nlgnPowMod(a,n/2,m); long long mod=(long long )ret*ret%m; if(n%2==1) { mod=(mod*a)%m; } return (int)mod; }}int main(){ //最大公约数gcd() cout<<gcd(30,14)<<endl; //最小公倍数lcm() cout<<lcm(5,9)<<endl; //打1.....1e6的素数表 int cnt=prime(10); for(int i=0;i<cnt;++i) { cout<<p[i]<<","; } cout<<endl; //求解形如：ax+by+c=0 的整系数线性方程 int a=6,b=15,c=9,x,y; if(result(a,b,c,x,y)) { cout<<"其中一组解为："<<x<<","<<y<<endl; } //大整数取模 // memset(input,0,sizeof(input)); // cin>>input; //cout<<bigMod(input,100); //幂取模 cout<<nPowMod(2,100000,500)<<endl; cout<<nlgnPowMod(2,100000,500)<<endl; return 0;}
[解决办法]
// 普通的筛素数方法与改进之后的效率对比#include<iostream>#include<cmath>#include<cstdio>using namespace std;#include<memory.h>#include<time.h>const int MAXN = 10000000;bool flag[MAXN];int prime[664600], num; //10^7//int prime[5761500], num; //10^8int bit[MAXN / 32];// 利用对每个素数的倍数必定不是素数来筛选void GetPrime_1(){ int i, j; num = 0; memset(flag, false, sizeof(flag)); for (i = 2; i < MAXN; ++i) { if (!flag[i]) { prime[num++] = i; for (j = i; j < MAXN; j += i) flag[j] = true; } } cout<<num<<endl;}// 利用了奇偶性来筛选void GetPrime_2(){ int i, j; prime[0] = 2; num = 1; memset(flag, false, sizeof(flag)); for (i = 3; i < MAXN; i+=2) { if (!flag[i]) prime[num++] = i; for (j = i; j < MAXN; j += i) { if(!flag[j]) flag[j] = true; } } cout<<num<<endl;}void GetPrime_3() { int i,j,k,flag; prime[0] = 2; num = 1; for(i = 3 ; i < MAXN ; i += 2) //奇数才有可能是素数，偶数就可以直接忽略了 { k = sqrt(i*1.0); flag = 0; for(j = 3 ; j <= k ; j += 2) //奇数肯定无法整除偶数，所以只需要判断是否能否整除奇数就可以了，只要有一个能够整除，就不是素数 { if(i % j == 0) { flag = 1; break; } } if(flag == 0) prime[num++] = i; } cout<<num<<endl;}// 利用了每个合数必有一个最小素因子来筛选// 方法最快的筛选方法void GetPrime_4(){ int i, j; num = -1; memset(flag, false, sizeof(flag)); for (i = 2; i < MAXN; ++i) { if (!flag[i]) prime[++num] = i; for (j = 0; j <= num && i * prime[j] < MAXN; ++j) { flag[i * prime[j]] = true; if (i % prime[j] == 0) //这句保证每个非素数只被筛去一次 break; } } cout<<num<<endl;}//位操作void GetPrime_5(){ int i, j; num = 0; memset(bit, 0, sizeof(bit)); for (i = 2; i < MAXN; i++) { if (!((bit[i / 32] >> (i % 32)) & 1)) { prime[num++] = i; for (j = i; j < MAXN; j += i) bit[j / 32] |= (1 << (j % 32)); } } cout<<num<<endl;}int main(void){ printf(" 在%d的数据量下普通的筛素数方法与改进之后的效率对比\n", MAXN); clock_t clockBegin, clockEnd; clockBegin = clock(); GetPrime_1(); clockEnd = clock(); printf("普通的筛素数方法\t%d毫秒\n", clockEnd - clockBegin); clockBegin = clock(); GetPrime_2(); clockEnd = clock(); printf("具有奇偶性的筛素数方法\t%d毫秒\n", clockEnd - clockBegin); clockBegin = clock(); GetPrime_3(); clockEnd = clock(); printf("筛素数方法\t%d毫秒\n", clockEnd - clockBegin); clockBegin = clock(); GetPrime_4(); clockEnd = clock(); printf("改进的筛素数方法\t%d毫秒\n", clockEnd - clockBegin); clockBegin = clock(); GetPrime_5(); clockEnd = clock(); printf("位操作筛素数方法\t%d毫秒\n", clockEnd - clockBegin); system("pause"); return 0;}