//Generates Prime using Seive of Eratosthenes Idea

Updated mrnutty 0 393 Views

It uses the idea of Seive of Eratosthenes.

The code is basically does the following to find Prime Numbers :

1) Populate Array from 0 - > MAX
2) Find 1st Prime, which is 2
3) Delete all Multiple of 2, i.e set it to false
4) Find next prime, which is 3
5) Delete all multiple of 3
6) Repeat steps 4 - 6 until done.

I also use a little try and catch, just to provide as an example.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::cin;

//Helper
typedef unsigned int uInt; 
typedef std::vector<bool> boolVec;

//Generates Prime using Seive of Eratosthenes Idea
void SeivePrime(const uInt MAX)
{
	if(MAX < 1 || MAX > INT_MAX){
		throw std::invalid_argument("Number not within range[2,INT_MAX] to call SeivePrime(const unsigned int)\n\n");
	}

	boolVec Prime(MAX + 1, true);
	//0,1 is not a Prime
	Prime[0] = Prime[1] = false;
	
	uInt nextPrime = 2;	
	bool deleteComplete = false;

	//Heart of the code
	//Helps generate prime numbers
	while(nextPrime <= MAX)
	{
		//delete all multiple of nextPrime		
		for(uInt i = 2; !deleteComplete; i++)	{			
			if( nextPrime * i > MAX  )
				deleteComplete = true;
			else Prime[nextPrime * i] = false;
		}

		//reset for next use
		deleteComplete = false;

		//Find next prime
		++nextPrime;
		while(nextPrime <= MAX && !Prime[nextPrime]) { 			
			++nextPrime;
			continue;
		}		
	
	}

	//Display Prime
	uInt i = 0;
	while(i <= MAX)	
	{		
	   if(Prime[i])
	     cout<< i <<" is a Prime\n";						
	   ++i;
	}

}
int main()
{ 

	try	{		
		SeivePrime(1438);
	}
	catch(std::exception& e){
		cout << e.what() <<endl;
	}
	
	return 0;

}

Dani AI

Generated

Nice start — the submission shows the sieve idea and is a good teaching example. A few correctness, safety and performance tweaks make it robust for larger MAX values and clearer to read: fix the input-range check (primes start at 2), avoid multiplication-based overflow in the inner loop, stop sieving once the current prime exceeds sqrt(MAX), and prefer a byte array for tight inner loops (or keep vector<bool> for memory savings). Also note the common spelling: "Sieve" (not "Seive").

#include <iostream>
#include <vector>
#include <cmath>

std::vector<unsigned int> sieve_primes(unsigned int max) {
    if (max < 2) return {};
    std::vector<char> is_prime(max + 1, 1); // byte array often faster than vector<bool>
    is_prime[0] = is_prime[1] = 0;

    unsigned int limit = static_cast<unsigned int>(std::sqrt(max));
    for (unsigned int p = 2; p <= limit; ++p) {
        if (!is_prime[p]) continue;
        unsigned int start = p * p; // safe because p <= sqrt(max)
        for (unsigned int m = start; m <= max; m += p)
            is_prime[m] = 0;
    }

    std::vector<unsigned int> primes;
    for (unsigned int i = 2; i <= max; ++i)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

int main() {
    for (auto p : sieve_primes(1438)) std::cout << p << " is prime\n";
}

Notes and quick troubleshooting tips:

  • Start marking at p*p to avoid re-marking multiples already handled by smaller primes.
  • Stop increasing p once p > sqrt(MAX); remaining unmarked entries are prime.
  • To avoid overflow on the start value when using very large types, compute start as size_t start = static_cast<size_t>(p) * p and check start <= max.
  • vector<bool> packs bits (good for memory) but has a proxy reference type that can slow tight loops; vector<char> or a bitset library can be faster.
  • For very large ranges (memory limits or MAX > 1e8), use a segmented sieve or wheel factorization to keep RAM use reasonable.
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview