运行时间打印出所有在N素数 [英] running time for print out all primes under N

问题描述

  INT主要（）{
      INT I，A [N];
      //初始化数组
      为（ⅰ= 2; I＆所述N;我+ +）A [1] = 1;
      对于（i = 2;我n种;我++）
         如果（A [1]）
              对于（INT J =;Ĵ* I n种; J ++）一[I * J] = 0;
       // pirnt质数少则N
       对于（i = 2;我n种;我++）
           如果（A [1]）COUT＆LT;＆LT; ＆LT;＆LT;一世;
       COUT＆LT;＆LT; ENDL;
}
 

这是在算法的书给我读了上面的程序运行时间是成正比的 N + N / 2 + N / 3 + N / 5 + N / 7 + N / 11 + .. ，

请帮助我了解如何笔者来到了从程序上面的等式。 谢谢！ Venkata

解决方案

这是筛埃拉托色尼的方法寻找素数。对于每一个素数，则若（a [i]）测试成功，并在内部循环被执行。考虑这个内循环的每一步是如何终止（记住，病情Ĵ* I＆LT; N ，或者等价地， J＆LT; N / I ）：

• 设为i = 2 - > J = 2，3​​，4，...，N / 2
• I = 3 - > J = 3，4，5，...，N / 3
• I = 4 - >不是素数
• I = 5 - > J = 5，6，7，...，N / 5
• ...

求和操作（包括初始化所述阵列/提取的素数）的总数给出书中提到的运行时间。

请参阅<一href="http://stackoverflow.com/questions/2582732/time-complexity-of-sieve-of-eratosthenes-algorithm">this问题了解，包括如何在位运算而言，这变成邻扩展（N（log n）的（日志日志N））的讨论，具体根据的维基百科的文章。

int main() {
      int i, a[N];
      // initialize the array
      for(i = 2; i < N; i++) a[i] = 1;
      for(i = 2; i < N; i++)
         if(a[i])
              for(int j = i; j*i < N; j++) a[i*j] =0;
       // pirnt the primes less then N
       for(i = 2; i < N; i++)
           if(a[i]) cout << "  " << i;
       cout << endl;
}

It was given in algorithm book i am reading running time of above program is proportional to N+N/2+N/3+N/5+N/7+N/11+...,

Please help me in understanding how author came up with above equation from the program. Thanks! Venkata

解决方案

This is the "Sieve of Eratosthenes" method for finding primes. For each prime, the if(a[i]) test succeeds and the inner loop gets executed. Consider how this inner loop terminates at each step (remember, the condition is j*i < N, or equivalently, j < N/i):

• i = 2 -> j = 2, 3, 4, ..., N/2
• i = 3 -> j = 3, 4, 5, ..., N/3
• i = 4 -> not prime
• i = 5 -> j = 5, 6, 7, ..., N/5
• ...

Summing the total number of operations (including initialising the array/extracting the primes) gives the runtime mentioned in the book.

See this question for more, including a discussion of how, in terms of bit operations, this turns into an expansion of O(n(log n)(log log n)) as per the Wikipedia article.

这篇关于运行时间打印出所有在N素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！