Check if a Number Is Prime

Check if a Number Is Prime
There are several methods for testing primality of integers. The best choice depends on the circumstances. Some of the methods are faster than others, while some popular tests are actually only probabilistic algorithms that will occasionally falsely characterize a number as prime or composite. The faster methods are primality tests, not factorization algorithms, so even if they show a number to be composite, they reveal nothing about its prime factors. This article will help you to explore a few of the methods.

Steps


Trial division

  1. Trial division is the simplest test for primality. It is based on the definition of a prime number. A number is prime if it has no divisors other than itself and one.

  2. Let n be the number you want to test.
  3. Divide n by 2. If the result is an integer, then n is not prime because 2 is a factor of n. Look at the last digit and if it's an even number, it's divisible by 2. If not, continue.
  4. Divide n by 3. If the result is an integer, then n is not prime because 3 is a factor of n. If not, continue.
  5. Continue dividing n by each number between 2 and n1/2 inclusive. If any of them divide evenly, then n is not prime because you found a factor. If n has no factors less than its square root, then n is prime. It is sufficient to check only for divisors less than or equal to n1/2 because if n = a*b, then a and b can't both exceed the square root of n.
  6. 6
    This can be optimised by skipping the test division by numbers which are obviously not prime. For example, skip every even number greater than two and every multiple of three greater than three.

Fermat's Little Theorem

  1. Technically, Fermat's test is a test for compositeness, rather than for primeness. This is because, if the test fails, the number is certainly composite, but if the test passes, the number is very likely prime, but might possibly be a composite pseudoprime.
  2. Let n be the number to test for primality.
  3. Pick any integer a between 2 and n-1.
  4. Compute an (mod n).
    • Compute this efficiently by using squaring instead of multiplication whenever possible. That is, compute 3100 as (((((((32)*3)2)2)2)*3)2)2, not as 3*3*3*3*...*3. Reduce modulo n after each operation.
  5. Check whether an = a (mod n). If not, n is composite. If true, n is likely prime. Repeating the test with different values for a can increase the confidence in the outcome, though there are rare composite numbers that satisfy the Fermat condition for all values of a. These pseudoprimes are the Carmichael numbers and the smallest is 561.

Miller-Rabin

  1. The Miller-Rabin test works similarly to Fermat's but handles pathological cases like the Carmichael numbers better.
  2. Let n be an odd number to test for primality.
  3. Factor all powers of 2 from n-1, expressing it in the form n-1 = 2s*d where d is odd.
  4. Pick a random number a between 2 and n-1.
  5. Compute ad (mod n). If ad = 1 or -1 (mod n), then n passes the Miller-Rabin test and is probably prime.
  6. Otherwise, compute a2d, a4d, ... and a2s-1d. If one of these equals -1 (mod n), then n is also passes and is probably prime.
  7. If n passes the Miller-Rabin test for some value of a, try another a to improve the confidence in the outcome of the test.
  8. If n is in fact prime, it will pass with any value of a. If n is composite, it will fail for at least three quarters of the values of a.
    Best rates. Fast payments Start today. 50 terminations.
  • The 168 prime numbers under 1000 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 
  • While trial division is slower than more sophisticated methods for large numbers, it is still quite efficient for small numbers. Even for primality testing of large numbers, it is not uncommon to first check for small factors before switching to a more advanced method when no small factors are found.

A math website kids LOVE — Win awards, certificates, have fun!

Things You'll Need

  • Working out tools, such as paper and pen or a computer

Comments

Post a Comment

THANKS FOR your opinion in this article