Check Prime Number & Print all prime numbers smaller than N

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Ex: 2 3 5 7 11 ….

2: 2%1 == 0 and 2%2 == 0 -> True.

3: 3%1 == 0 and 3%3 == 0 -> True.

4: 4%1 == 0 and 4%2 == 0 and 4%4 == 0 -> False (remember: natural number greater than 1 that has no positive divisors other than 1 and itself.)

This function below for checking if an integer number is prime or NOT:

==========================================================================


bool CheckPrime(int number)
{
if(number < 2){ return false; } else if(number > 2){
if(number % 2 == 0){ return false; }
for(int i = 3; i*i<=number; i += 2){
if(number % i == 0){ return false; }
}
}
return true;
}

print all prime numbers smaller than N:

find out: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s