將素數過濾代碼-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。

如果你願意，你可以優化我所做的一些。