一种求素数算法的时间复杂度

Question

我对素数很好奇，我想知道在1000万范围内找到相对较小的素数的最有效方法。我读过一篇文章说，Eratosthenes筛（SOE）是找到更小质数的最有效方法。我使用python实现了SOE，但有几个问题：

1. 我的算法最坏的运行时间似乎是O（n^2）。我还在学习，所以我知道这个算法可以提高效率。

2. 寻找素数的最有效的数学方法和最有效的编程方法有区别吗？从数学上讲，SOE是最快的之一，但是编程方面的SOE有那么快吗？在

   def FindPrime(n):
       primes = [2, 3]
       for num in range(4, n):
           notprime = False
           for p in primes:
               if num % p == 0:
                   notprime = True
           if notprime == False:
               primes.append(num)
   
       print primes
   
   print FindPrime(100)
   

Answer 1

首先，您应该知道您的算法不是sieve of Eratosthenes。你在用审判庭。在

可以对您的实现进行一些改进。在

1. 使用xrange()，这是O(1)内存方面的，而不是{}，它是{}。

2. 在搜索中跳过偶数：xrange(4, n, 2)每次第2步。

3. 当p > sqrt(n)时，不要测试质数p是否除以n。这是不可能的。

正如您所预测的，这些更改不会影响复杂性的顺序，但是您将看到一个可靠的性能改进。在

至于更快的算法，首先实现一个真正的Eratosthenes筛，然后尝试更快的sieve of Atkin。在

Answer 2

1. uʍopǝpısdn是对的，您的代码不是SOE

2. 您可以找到我的SOE实现here

   • 这使得寻找素数比你的解更有效

3. 国有企业矿山实施的复杂性

   • 时间：T(0.5·n·DIGAMMA(CEIL(SQRT(n))+0.3511·n)如果sqrt（N）像代码内注释中建议的那样使用
   • 时间（n=1M）：T(3.80*n)
   • 时间（n=10M）：T(4.38*n)
   • 时间（n=100M）：T(4.95*n)
   • 时间（n=1000M）：T(5.53*n)
   • 所以大约运行时间是：T((0.3516+0.5756*log10(n))*n)
   • 所以复杂性是O(n.log(n))

4. 速度（运行时）和复杂性O（）之间的差异

   • 实际运行时是t=T(f(n))*c
   • 对于足够大的n，它收敛到t=O(f(n))*c
   • 其中O()是算法的时间复杂度
   • 并且T()是任意n的实际运行时方程（不是O()！！！）在
   • c是一个固定的时间，它需要处理所有for中的单个焊道等。。。在
   • 更好的O()并不意味着更快的解决方案
   • 对于任何n，仅在treshold where之后
   • O1(f1(n))*c1 < O2(f2(n))*c2
   • 因此，如果你很好地优化了c常数，那么你就可以击败复杂度更好的算法，达到一个树形图
   • 例如，您的代码大约是T(n.n/2)->；O(n^2)
   • 但是对于低氮，可以比我的SOE快O(n.log(n))
   • 因为我需要准备表格，这比你的除法要花更多的时间
   • 但是在那之后你的速度会慢得多。。。在

所以对于最有效的数学和编程解决方案之间是否存在差异的问题

• 答案是是它可以在定义的N-范围上存在

Answer 3

你可以使用快速的反根算法，它包含了一点比特黑客攻击，在O（c）中找到一个数的平方根，然后在O（n^（1/2））中找到它是否素数，然后在你的问题中，你可以在O（n*（n^（1/2）））中找到间隔的素数，它比O（n^2）好，如果我们看看你提到的算法，它是列表的最佳方法（有界）0-something）因为它不会对任何值进行两次检查，并且它的时间复杂性可以降低到O（（n^（1/2））*log（log（n））/log（n）），并且它可以用于创建查找表，并且您的实现在一定程度上是错误的，所以我用c++编写示例，您可以使用它：

float root( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 3rd iteration, this can be removed

    return 1/y;
}


void seo(int ub){//ub->upper bound should be at least 2
    if(ub<2)
        return;
    int size=ub-1;
    int *arr=new int[size];
    for(int i=0;i<size;i++){
        arr[i]=i+2;
    }
    int outer_ub=((int)root((float)ub))-1;
    for(int j=0;j<outer_ub;j++){
        if(arr[j]>0){
            int inc=arr[j];
            for(int i=inc+j;i<size;i+=inc){
                arr[i]=0;
            }
        }
    }
    for(int i=0;i<size;i++){
        if(arr[i]!=0)
            cout<<arr[i]<<endl;
    }
}