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

## Post a Comment