Sieve of the Eratosthenes algorithm

Question

I am currently reading "Programming: Principles and Practice Using C ++", in chapter 4 there is an exercise in which:

I need to make a program to calculate primes from 1 to 100 using the Sieve of Eratosthenes algorithm.

This is the program I came up with:

#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; } 

Not the best or fastest, but I'm still in the early stages of the book and know little about C ++.

Now the problem is, until max is more than 500 , all values ​​will be printed on the console, if max > 500 not all will be printed.

Am I doing something wrong?

PS: Any constructive criticism will also be appreciated.

Answer 1

I have no idea why you are not getting the whole result, since it looks like you should get everything. What result are you missing?

The grill is not made correctly. Sort of

 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; } } } 

will implement a sieve. (The code above, written from my head, is not guaranteed to work or even compile. I do not think that at the end of chapter 4 he received nothing that was not.)

Return the primes as usual and print all the contents.

Answer 2

Think of a sieve as a set.
Go through the set in order. For each value in thesive, delete all numbers that are shared with it.

 #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. // ie It prints all the primes. std::copy(sieve.begin(),sieve.end(),std::ostream_iterator<int>(std::cout,"\n")); } 

Answer 3

From 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 4

Interestingly, no one answered your question about the exit problem. I do not see anything in the code, which should influence the result depending on the value of max.

For what it's worth, on my Mac I get all the output. This is wrong, of course, since the algorithm is wrong, but I get everything. You did not mention which platform you are running on, which may be useful if you continue with release issues.

---

Here is a version of your code minimally modified to follow the actual sieve algorithm.

 #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 5

In the code snippet below, numbers are filtered before they are inserted into vector . Divisors come from a vector.

I also pass the vector by reference. This means that the huge vector will not be copied from the function to the caller. (Large chunks of memory take a long time to copy)

 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); } } } 

This is not the most efficient algorithm, but it follows the sieve algorithm.

Answer 6

below is my version, which mainly uses the bool bit vector, and then goes through odd numbers and a quick add to find the factors to set to false. As a result, the vector is built and returned to the client with the basic values.

 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 7

Here is a brief, well-explained implementation using the bool type:

 #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, ie 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, ie 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 <<" "; } } } 

spanning an array. The implementation of A std::vector will include minor changes, such as reducing functions to one parameter, through which the vector is passed by reference, and loops will use the member function size() instead of the reduced parameter.

Answer 8

Here is a more efficient version for the Sieve of Eratosthenes algorithm that I implemented.

 #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 9

Here my implementation is not sure if 100% is correct though: 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 10

I am following the same book now. I came up with the following implementation of the algorithm.

 #include<iostream> #include<string> #include<vector> #include<algorithm> #include<cmath> using namespace std; inline void keep_window_open() { char ch; cin>>ch; } int main () { int max_no = 100; vector <int> numbers (max_no - 1); iota(numbers.begin(), numbers.end(), 2); for (unsigned int ind = 0; ind < numbers.size(); ++ind) { for (unsigned int index = ind+1; index < numbers.size(); ++index) { if (numbers[index] % numbers[ind] == 0) { numbers.erase(numbers.begin() + index); } } } cout << "The primes are\n"; for (int primes: numbers) { cout << primes << '\n'; } } 

Answer 11

Here is my version:

 #include "std_lib_facilities.h" //helper function:check an int prime, x assumed positive. bool check_prime(int x) { bool check_result = true; for (int i = 2; i < x; ++i){ if (x%i == 0){ check_result = false; break; } } return check_result; } //helper function:return the largest prime smaller than n(>=2). int near_prime(int n) { for (int i = n; i > 0; --i) { if (check_prime(i)) { return i; break; } } } vector<int> sieve_primes(int max_limit) { vector<int> num; vector<int> primes; int stop = near_prime(max_limit); for (int i = 2; i < max_limit+1; ++i) { num.push_back(i); } int step = 2; primes.push_back(2); //stop when finding the last prime while (step!=stop){ for (int i = step; i < max_limit+1; i+=step) {num[i-2] = 0; } //the multiples set to 0, the first none zero element is a prime also step for (int j = step; j < max_limit+1; ++j) { if (num[j-2] != 0) { step = num[j-2]; break; } } primes.push_back(step); } return primes; } int main() { int max_limit = 1000000; vector<int> primes = sieve_primes(max_limit); for (int i = 0; i < primes.size(); ++i) { cout << primes[i] << ','; } } 

Answer 12

Here is a classic method for this,

 int main() { int max = 500; vector<int> array(max); // vector of max numbers, initialized to default value 0 for (int i = 2; i < array.size(); ++ i) // loop for rang of numbers from 2 to max { // initialize j as a composite number; increment in consecutive composite numbers for (int j = i * i; j < array.size(); j +=i) array[j] = 1; // assign j to array[index] with value 1 } for (int i = 2; i < array.size(); ++ i) // loop for rang of numbers from 2 to max if (array[i] == 0) // array[index] with value 0 is a prime number cout << i << '\n'; // get array[index] with value 0 return 0; } 

Answer 13

Try this code, it will be useful to you using 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]; } }