42. TEST FOR PRIMES
 
Home Menu Previous Next


Quickly Eliminate non-Primes:
1. Number to end in 1, 3, 7 or 9.

2. May apply the divide by 6 test.
    Remainder to be 1 or 5 when divided by 6.

The Actual Test:
3. Apply the division test.
   Divide by primes, upto the square-root of the largest square, which is less than the number being tested.
Not to be divisible.

Examples:
Squares of primes:

22325272112132172...
492549121169289...

[For squaring numbers, see QM techniques.]

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

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

iii. Test 107
72 is 49; 112 is 121
So test divisibility by upto 7.

iv. Test 171
132 is 169; 172 is 289
So test divisibility by upto 13.

v. Test 823
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 divisibility tests.
    [See following pages.]

<<< Becoming Ramanujan