To identify wether a number N is prime or not, till what number the divisibility must be checked?

If a number is composite then it should be divisible by any one of the primes less then or equal to the numbers square root.

that is if a is composite number, then there should exist a number b which is less than √a which divides a.

this b should be a prime number.

So check the divisibility of a number by primes which are less than its square root.

For example: To determine whether 667 is prime or not

√667≈25 so if 667 is composite, then it should have a prime divisor less than 25

and 23|667, 23 is less than 25. So 667 is a composite.

Hi Speed Racer,

One needs to check for divisibility upto [√N], where [.] denotes the greatest integer function.

This is simply because, for any given nuber N, if it is composite, one factor will be ≤ √N, and the other will ≥ √N.

Hope it helps.

Regards,

Ashwin (IIT MadraS).