将素数过滤代码-O（n^2）改为O（n）并删除数组中的冗余元素

Question

我创建的这段代码迭代了数字1-100，并消除了非素数，即树叶2,3,5 .. 97。但是，它包含2个用于排序算法的循环，因此速度很慢。最重要的是，数字“0”保留在被淘汰的数字中。

我的问题是，我该如何将这个程序带到O（n）性能，以及如何将nums []中的素数复制到另一个数组中，以便它们处于有序状态？

#include <stdio.h> 

#define MAX 100 

int main() 
{ 
    int nums[MAX]; 
    int i,j; 

    for (i=0;i<MAX;i++) 
    { 
     nums[i] = i; //Place numbers from 1 to 100 in the array 
    } 

    for (i=0;i<MAX;i++) //Loops through each number in the array 
    { 
     for (j=2;j<=9;j++) 
      /* This loop iterates from 2 to 9 and checks if 
      the current number is divisible by it. If it is, 
      it replaces it with 0.*/ 
     { 
      if (nums[i] == 1 || nums[i] == 4 || nums[i] == 6 || nums[i] == 8 || nums[i] == 9 || nums[i] == 10) 
      /*Excludes non-primes less than 11*/ 
      { 
       nums[i] = 0; 
      } 

      if ((nums[i]%j)==0 && nums[i] > 11) 
      { 

       nums[i] = 0; 
      } 
     } 
    } 

    for (i=0;i<MAX;i++) 
    { 
     printf("%d ", nums[i]); 
    } 
    return 0; 
} 

感谢您的帮助提前！

Answer 1

是的，有O(N)主发电机在那里（其中N是质量数，而不是在亚线性时间内运行的质量数的范围大小）。例如欧拉公式（从项目欧拉27）：公式的输出

p = n² + n + 41; n={0,1,2,...39} 

这里比较对素数：

Output: 41,43,47,53,...61,...71,......83,...97,................113,....131,............151,............173,................197,........223,....................251,....................281,................313,............347,........................383,....................421,........................461,........................503,................547,........................593,............................641,................................691,........................743,........................797,............................853,................................911,............................971,.........................................1033,.............................................1097,...................................1163,...................................1231,.......................................................1301,...................................1373,........................................1447,.......................................................1523,..................................................1601 
Primes: 41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601 

正如你可以看到它产生为了素数，但不是所有的人。这种发生器限于特定的范围。还有数字方法可以在特定范围内生成此类公式，但要获得它们比O(N)困难得多。

你需要的是做一个近似多项式，它可以在<1,100>上工作，但是为了保持精度（或者明智地使用它），可能需要高次多项式。所以谷歌多项式拟合但更好的选择将是PSLQ。

有关如何提高筛黄金发生器看看更多的想法：

• Prime numbers by Eratosthenes quicker sequential than concurrently?

Answer 2

我不知道你打算做什么。但是，如果它是一个主要的发电机，然后看看你的代码if ((nums[i]%j)==0 && nums[i] > 11)nums[i] = 0这个条件。如果我没有错，就在这里筛选非素数。是的，它会正确地过滤波纹管100。但是11或13的数倍可以说121或169这些不会过滤掉非素数。然后，您必须在检查器中添加更多数字。所以它不是一个好的过滤器。
让设计滤波器:)，你知道所有的素数是奇数，除了2

所以首先从我们list.Lets说我们有0的数组，我们筛选过后，我们会过滤所有偶数哪个指数将保持0是素数。

for(int a=4; a<MAX; a+=2)nums[a]=1; 
//remove all even(multiple of 2) number, except 2 

现在我们要滤除多个疗法奇怪的像9,15,121等 的赔率让我们从第一奇NUM启动和过滤他们的倍数

for(int a=3; a<MAX; a+=2) //all odd num below MAX 
{ 
    for(int b=a*2; b<MAX; b+=a)nums[b]=1; 
    //multiple of a's are a*2,a*2+a,a*2+a+a .... 
} 

所以在这个循环中，当我们正在获取一个奇数，我们正在过滤它的所有倍数。所以所有没有被滤除的奇数都是主因，除了1和它本身之外，它们没有除数。

我们检查过NUMS阵列结果环路指数仍在0

for(int a=2;a<MAX; a++)if(!nums[a])printf("%d ", a); 

是的，你明白我的意思，我认为这种做法称为sieve of Eratosthenes。

如果你愿意，你可以优化我所做的一些。