42. TEST FOR PRIMES | |||
---|---|---|---|

Home | Menu | Previous | Next |

Quickly Eliminate non-Primes:

1. Number to end in

2. May apply the

The Actual Test:

3. Apply the

Divide by primes, upto the square-root of the largest square, which is less than the number being tested.

Examples:

2^{2} | 3^{2} | 5^{2} | 7^{2} | 11^{2} | 13^{2} | 17^{2} | ... |

4 | 9 | 25 | 49 | 121 | 169 | 289 | ... |

Largest sq. is 121; root is 11; so test dividing by upto 11. i.e. Test divide 151 by 3, 7 and 11.

Largest sq. is 169; root is 13; so test dividing by upto 13. i.e. Test divide 283 by 3, 7, 11 and 13.

72 is 49; 112 is 121

So test divisibility by upto 7.

132 is 169; 172 is 289

So test divisibility by upto 13.

232 is 529; 292 is 841

So test divisibility by upto 23.

i.e. by 3, 7, 11, 13, 17, 19, 23

4. We do not have to actually divide.

Enough to use the