埃拉托色尼算法的篩

Question

我目前正在讀「編程：原理與實踐使用C++」，在第4章存在這樣的練習：

我需要一個程序來計算素數字介於1到100之間，使用Eratosthenes算法篩選。

這是我想出了程序：

#include <vector> 
#include <iostream> 

using namespace std; 

//finds prime numbers using Sieve of Eratosthenes algorithm 
vector<int> calc_primes(const int max); 

int main() 
{ 
    const int max = 100; 

    vector<int> primes = calc_primes(max); 

    for(int i = 0; i < primes.size(); i++) 
    { 
     if(primes[i] != 0) 
      cout<<primes[i]<<endl; 
    } 

    return 0; 
} 

vector<int> calc_primes(const int max) 
{ 
    vector<int> primes; 

    for(int i = 2; i < max; i++) 
    { 
     primes.push_back(i); 
    } 

    for(int i = 0; i < primes.size(); i++) 
    { 
     if(!(primes[i] % 2) && primes[i] != 2) 
      primes[i] = 0; 
     else if(!(primes[i] % 3) && primes[i] != 3) 
      primes[i]= 0; 
     else if(!(primes[i] % 5) && primes[i] != 5) 
      primes[i]= 0; 
     else if(!(primes[i] % 7) && primes[i] != 7) 
      primes[i]= 0; 
    } 

    return primes; 
} 

沒有最好或最快的，但我在書中還早，不知道很多關於C++。

現在的問題，直到max不大於500所有打印在控制檯上的值，如果max > 500不是所有的打印。

我做錯了什麼？

P.S .:還有任何建設性的批評將不勝感激。

Answer 1

我不知道爲什麼你沒有得到所有的輸出，因爲它看起來像你應該得到的一切。你錯過了什麼輸出？

篩網實施錯誤。像

vector<int> sieve; 
vector<int> primes; 

for (int i = 1; i < max + 1; ++i) 
    sieve.push_back(i); // you'll learn more efficient ways to handle this later 
sieve[0]=0; 
for (int i = 2; i < max + 1; ++i) { // there are lots of brace styles, this is mine 
    if (sieve[i-1] != 0) { 
     primes.push_back(sieve[i-1]); 
     for (int j = 2 * sieve[i-1]; j < max + 1; j += sieve[i-1]) { 
      sieve[j-1] = 0; 
     } 
    } 
} 

將執行篩。 （上面的代碼寫在了我的頭上;不保證能夠正常工作，甚至不能編譯，我認爲第4章末尾沒有任何內容。）

返回primes像往常一樣，並打印出整個內容。

Answer 2

從Algorithms and Data Structures：

void runEratosthenesSieve(int upperBound) { 
     int upperBoundSquareRoot = (int)sqrt((double)upperBound); 
     bool *isComposite = new bool[upperBound + 1]; 
     memset(isComposite, 0, sizeof(bool) * (upperBound + 1)); 
     for (int m = 2; m <= upperBoundSquareRoot; m++) { 
      if (!isComposite[m]) { 
        cout << m << " "; 
        for (int k = m * m; k <= upperBound; k += m) 
         isComposite[k] = true; 
      } 
     } 
     for (int m = upperBoundSquareRoot; m <= upperBound; m++) 
      if (!isComposite[m]) 
        cout << m << " "; 
     delete [] isComposite; 
} 

Answer 3

在下面的代碼段中，它們被插入到vector之前進行過濾的數字。除數來自矢量。

我也通過了參考向量。這意味着巨大的向量不會從函數複製到調用者。 （大塊內存多久時間來複制）

vector<unsigned int> primes; 

void calc_primes(vector<unsigned int>& primes, const unsigned int MAX) 
{ 
    // If MAX is less than 2, return an empty vector 
    // because 2 is the first prime and can't be placed in the vector. 
    if (MAX < 2) 
    { 
     return; 
    } 

    // 2 is the initial and unusual prime, so enter it without calculations. 
    primes.push_back(2); 
    for (unsigned int number = 3; number < MAX; number += 2) 
    { 
     bool is_prime = true; 
     for (unsigned int index = 0; index < primes.size(); ++index) 
     { 
      if ((number % primes[k]) == 0) 
      { 
       is_prime = false; 
       break; 
      } 
     } 

     if (is_prime) 
     { 
      primes.push_back(number); 
     } 
    }  
} 

這不是最有效的算法，但它遵循篩算法。

Answer 4

把篩子想象成一組。
按順序瀏覽設置。對於每個值，都可以刪除所有可以被它整除的數字。

#include <set> 
#include <algorithm> 
#include <iterator> 
#include <iostream> 


typedef std::set<int> Sieve; 

int main() 
{ 
    static int const max = 100; 

    Sieve sieve; 

    for(int loop=2;loop < max;++loop) 
    { 
     sieve.insert(loop); 
    } 


    // A set is ordered. 
    // So going from beginning to end will give all the values in order. 
    for(Sieve::iterator loop = sieve.begin();loop != sieve.end();++loop) 
    { 
     // prime is the next item in the set 
     // It has not been deleted so it must be prime. 
     int    prime = *loop; 

     // deleter will iterate over all the items from 
     // here to the end of the sieve and remove any 
     // that are divisable be this prime. 
     Sieve::iterator deleter = loop; 
     ++deleter; 

     while(deleter != sieve.end()) 
     { 
      if (((*deleter) % prime) == 0) 
      { 
       // If it is exactly divasable then it is not a prime 
       // So delete it from the sieve. Note the use of post 
       // increment here. This increments deleter but returns 
       // the old value to be used in the erase method. 
       sieve.erase(deleter++); 
      } 
      else 
      { 
       // Otherwise just increment the deleter. 
       ++deleter; 
      } 
     } 
    } 

    // This copies all the values left in the sieve to the output. 
    // i.e. It prints all the primes. 
    std::copy(sieve.begin(),sieve.end(),std::ostream_iterator<int>(std::cout,"\n")); 

} 

Answer 5

有趣的是，沒有人似乎回答了有關輸出問題的問題。我沒有看到任何影響輸出的代碼，取決於max的值。

在Mac上，我得到了所有的輸出。這當然是錯誤的，因爲算法不正確，但我確實得到了所有的輸出。您沒有提及您正在運行的平臺，如果您仍然遇到輸出問題，這可能很有用。

---

這是您的代碼的一個版本，根據實際的Sieve算法進行最小修改。

#include <vector> 
#include <iostream> 

using namespace std; 

//finds prime numbers using Sieve of Eratosthenes algorithm 
vector<int> calc_primes(const int max); 

int main() 
{ 
    const int max = 100; 

    vector<int> primes = calc_primes(max); 

    for(int i = 0; i < primes.size(); i++) 
    { 
     if(primes[i] != 0) 
      cout<<primes[i]<<endl; 
    } 

    return 0; 
} 

vector<int> calc_primes(const int max) 
{ 
    vector<int> primes; 

    // fill vector with candidates 
    for(int i = 2; i < max; i++) 
    { 
     primes.push_back(i); 
    } 

    // for each value in the vector... 
    for(int i = 0; i < primes.size(); i++) 
    { 
     //get the value 
     int v = primes[i]; 

     if (v!=0) { 
      //remove all multiples of the value 
      int x = i+v; 
      while(x < primes.size()) { 
       primes[x]=0; 
       x = x+v; 
      } 
     } 
    } 
    return primes; 
} 

Answer 6

這是我實現的更高效的Eratosthenes Sieve算法。

#include <iostream> 
#include <cmath> 
#include <set> 

using namespace std; 

void sieve(int n){ 
    set<int> primes; 
    primes.insert(2); 
    for(int i=3; i<=n ; i+=2){ 
     primes.insert(i); 
    }  

    int p=*primes.begin(); 
    cout<<p<<"\n"; 
    primes.erase(p); 

    int maxRoot = sqrt(*(primes.rbegin())); 

    while(primes.size()>0){ 
     if(p>maxRoot){ 
      while(primes.size()>0){ 
       p=*primes.begin(); 
       cout<<p<<"\n"; 
       primes.erase(p);   
      } 
      break; 
     } 

     int i=p*p; 
     int temp = (*(primes.rbegin())); 
     while(i<=temp){ 
      primes.erase(i); 
      i+=p; 
      i+=p; 
     } 
     p=*primes.begin(); 
     cout<<p<<"\n"; 
     primes.erase(p); 
    } 
} 

int main(){ 
    int n; 
    n = 1000000; 
    sieve(n);     
    return 0; 
} 

Answer 7

使用java question bank

import java.io.*; 

class Sieve 

{ 

    public static void main(String[] args) throws IOException 

    { 

     int n = 0, primeCounter = 0; 

     double sqrt = 0; 

     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 


     System.out.println(「Enter the n value : 」); 

     n = Integer.parseInt(br.readLine()); 

     sqrt = Math.sqrt(n); 

     boolean[] prime = new boolean[n]; 

     System.out.println(「\n\nThe primes upto 」 + n + 」 are : 」); 

     for (int i = 2; i<n; i++) 

     { 

      prime[i] = true; 

     } 

     for (int i = 2; i <= sqrt; i++) 

     { 

      for (int j = i * 2; j<n; j += i) 

      { 

       prime[j] = false; 

      } 

     } 

     for (int i = 0; i<prime.length; i++) 

     { 

      if (prime[i]) 

      { 

       primeCounter++; 

       System.out.print(i + 」 「); 

      } 

     } 

     prime = new boolean[0]; 

    } 

} 

Answer 8

試試這個代碼，這將是對你有用這裏是我實現正確的，雖然不知道是否100％： http://pastebin.com/M2R2J72d

#include<iostream> 
#include <stdlib.h> 

using namespace std; 
void listPrimes(int x); 

int main() { 

    listPrimes(5000); 
} 

void listPrimes(int x) { 
    bool *not_prime = new bool[x]; 
    unsigned j = 0, i = 0; 

    for (i = 0; i <= x; i++) { 
     if (i < 2) { 
      not_prime[i] = true; 
     } else if (i % 2 == 0 && i != 2) { 
      not_prime[i] = true; 
     } 
    } 

    while (j <= x) { 
     for (i = j; i <= x; i++) { 
      if (!not_prime[i]) { 
       j = i; 
       break; 
      } 
     } 
     for (i = (j * 2); i <= x; i += j) { 
      not_prime[i] = true; 
     } 
     j++; 
    } 

    for (i = 0; i <= x; i++) { 
     if (!not_prime[i]) 
      cout << i << ' '; 
    } 

    return; 
} 

Answer 9

下面

是我的版本它基本上使用bool的位向量，然後通過奇數和快速添加找到倍數設置爲false。最後，一個向量被構造並返回到素數值的客戶端。

std::vector<int> getSieveOfEratosthenes (int max) 
{ 
    std::vector<bool> primes(max, true); 
    int sz = primes.size(); 

    for (int i = 3; i < sz ; i+=2) 
    if (primes[i]) 
     for (int j = i * i; j < sz; j+=i) 
     primes[j] = false; 

    std::vector<int> ret; 
    ret.reserve(primes.size()); 
    ret.push_back(2); 

    for (int i = 3; i < sz; i+=2) 
    if (primes[i]) 
     ret.push_back(i); 

    return ret; 
} 

Answer 10

下面是使用bool類型的簡明，很好地解釋實現：

#include <iostream> 
#include <cmath> 

void find_primes(bool[], unsigned int); 
void print_primes(bool [], unsigned int); 

//========================================================================= 
int main() 
{ 
    const unsigned int max = 100; 
    bool sieve[max]; 

    find_primes(sieve, max); 

    print_primes(sieve, max); 
} 
//========================================================================= 

/* 
    Function: find_primes() 
    Use: find_primes(bool_array, size_of_array); 

    It marks all the prime numbers till the 
    number: size_of_array, in the form of the 
    indexes of the array with value: true. 

    It implemenets the Sieve of Eratosthenes, 
    consisted of: 

    a loop through the first "sqrt(size_of_array)" 
    numbers starting from the first prime (2). 

    a loop through all the indexes < size_of_array, 
    marking the ones satisfying the relation i^2 + n * i 
    as false, i.e. composite numbers, where i - known prime 
    number starting from 2. 
*/ 
void find_primes(bool sieve[], unsigned int size) 
{ 
    // by definition 0 and 1 are not prime numbers 
    sieve[0] = false; 
    sieve[1] = false; 

    // all numbers <= max are potential candidates for primes 
    for (unsigned int i = 2; i <= size; ++i) 
    { 
     sieve[i] = true; 
    } 

    // loop through the first prime numbers < sqrt(max) (suggested by the algorithm) 
    unsigned int first_prime = 2; 
    for (unsigned int i = first_prime; i <= std::sqrt(double(size)); ++i) 
    { 
     // find multiples of primes till < max 
     if (sieve[i] = true) 
     { 
      // mark as composite: i^2 + n * i 
      for (unsigned int j = i * i; j <= size; j += i) 
      { 
       sieve[j] = false; 
      } 
     } 
    } 
} 

/* 
    Function: print_primes() 
    Use: print_primes(bool_array, size_of_array); 

    It prints all the prime numbers, 
    i.e. the indexes with value: true. 
*/ 
void print_primes(bool sieve[], unsigned int size) 
{ 
    // all the indexes of the array marked as true are primes 
    for (unsigned int i = 0; i <= size; ++i) 
    { 
     if (sieve[i] == true) 
     { 
      std::cout << i <<" "; 
     } 
    } 
} 

覆蓋陣列的情況。一個std::vector實現將包括一些細微的變化，如將函數減少爲一個參數，通過該參數向量通過引用傳遞，並且循環將使用成員函數向量而不是簡化參數。