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