C++ program to check whether a number is prime or not prime

A prime number is a whole number that is greater than one and the only factors of a prime number should be one and itself. Some of the first prime numbers are 2, 3, 5, 7, 11, 13 ,17 etc.

There can be many prime numbers between two intervals. For example, the prime numbers between the intervals 5 and 15 are 5, 7, 11 and 13

 

Some facts:

The only even prime number is 2. All other even numbers can be divided by 2.

If the sum of a number's digits is a multiple of 3, that number can be divided by 3.

No prime number greater than 5 ends in a 5. Any number greater than 5 that ends in a 5 can be divided by 5.

Zero and 1 are not considered prime numbers.

Except for 0 and 1, a number is either a prime number or a composite number. A composite number is defined as any number, greater than 1, that is not prime.

To prove whether a number is a prime number, first try dividing it by 2, and see if you get a whole number. If you do, it can't be a prime number. If you don't get a whole number, next try dividing it by prime numbers: 3, 5, 7, 11 (9 is divisible by 3) and so on, always dividing by a prime number

Example: C++ program to check whether a number is prime or not prime

Output

Enter a positive integer: 13
13 is a prime number

Optimized Method: C++ program to check whether a number is prime or not prime

Instead of checking till n, we can check till √n because a larger factor of n must be a multiple of smaller factor that has been already checked.
The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = ?1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1. (Source: wikipedia)

Output

Enter a positive integer: 13
13 is a prime number