# Finding prime numbers

### Description

**Prime number **is a natural number greater than one which can be divided only by 1 and itself without a remainder. For instance 2, 3, 5, 7, 11, 13, 17 and so on. Prime numbers are infinite.

In order to check if number is prime we need to divide this number by number from 2 to √n. If the algorithm will find a divider then given number is not prime. We will check numbers only to √n because if a number has any dividers, then we will always find a divider which is less than √n.

√24 ≈ 4,9

24 dividers are {1, 2, 3, 4, 6, 8, 12, 24}

Put 4,9 into this sequence – {1, 2, 3, 4, |4,9|, 6, 8, 12, 24}

As you can see the divider is always “on both sides” because6 = 24 : 4 → 4 = 24 : 6

In case of number that has natural square root the root will be the divider:

√25 = 525 dividers are {1, 5, 25}

### Input data

A natural number *n*.

### Output data

- 1 if
*n*is prime. - 0 if n isn’t prime.

### C++ code

1 2 3 4 5 6 7 8 9 10 | bool isPrime(int n) { if(n<2) return false; //If number is less than 2 it isn't prime. for(int i=2;i*i<=n;i++)//The loop break condition is i*i<=n because we check numbers only to square of n if(n%i==0) return false; //If algorithm will find divider, then the number is not prime. return true; } |