求第1000个素数解决方法

2012-10-21

求第1000个素数如题[解决办法] bool isprime1 在循环里没有重置。[解决办法]你忘了在第一个循环里让ispri

求第1000个素数
如题

[解决办法]
bool isprime=1; 在循环里没有重置。
[解决办法]
你忘了在第一个循环里让isprime变为1了

[解决办法]

探讨

还不想结帖，大家又没有什么更优化的算法呢？？？

[解决办法]
百度：筛法求素数。
[解决办法]
其实可以优化的，知道前面3个素数2，3，5
后面检验的就可以在原来素数的基础上+2，比如要找第四个素数
就在5的基础上+2，然后再用5+2整除前面的素数2，3，5如果都不能整除那就是素数
其他的以此类推
比一个个穷举快，检查方法也快了许多
[解决办法]
目前找素数的最快方法是筛选法，本人对筛选法进行了优化，使查找速度更快。下面是代码，可以跟任何一个算法进行比较，我都是最快的！

C/C++ code

#include <iostream>#include <math.h>using namespace std;int get_prime(int 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(55)<<endl;    return 0;}
[解决办法]
#include <iostream>
#include <math.h>
using namespace std;

int get_prime(int n)
{
int *p_r = new in……
[解决办法]
C/C++ code//获取n以内(含n)的所有质数，并返回质数的个数int TYCppStdLib::GetPrime(int n, vector<int> &vec){    vec.clear();    if(n<2)        return 0;    if(2==n)    {        vec.push_back(2);        return 1;    }    vec.push_back(2);    for(int i=3; i<=n; i=i+2)        if(IsPrime(i))            vec.push_back(i);    return static_cast<int>(vec.size());}

热点排行