Prime Number Tests
Date: 11/12/98 at 10:50:06 From: Natalie Subject: Prime Number Is the number 55409243 prime? Also, how can you test to see if a number is prime or not?
Date: 11/12/98 at 12:39:03 From: Doctor Rob Subject: Re: Prime Number No, 55409243 is not prime. You ask a very good question about testing for primality. There are quite a few ways to do that. They range from the very simple, yet time-consuming, to the very sophisticated and quite fast. The simplest way is to use Trial Division. Let N be the number in question to be tested. Divide by all prime numbers less than or equal to sqrt(N). If none go in evenly, then N is prime. In your case, you would divide by all the prime numbers less than 7443.73, of which there are more than 900. Here is a slightly more complicated way. 1) Pick any a with 1 < a < N-1. 2) Find the greatest common divisor d of a and N. If d > 1, then N is composite, and d is a factor. If d = 1, then compute the remainder of a^(N-1) when divided by N. If this is not 1, then N is composite. If this is 1, you can't tell if N is prime or not. Most composite numbers will be revealed to be composite by this method, however. This method is called the Fermat Test. In your case, I picked a = 3, and found that a^(N-1) left a remainder of 4483955 when divided by N, so N cannot be prime. This computation involved 26 squarings of 8-digit numbers, 15 multiplications by 3, and 26 divisions by N. This is slightly less work than 900-odd divisions of N by small primes. Some other ways involve trying to factor the number by various factoring algorithms, like Trial Division above, and either succeeding or failing. Still other ways depend on properties of prime numbers, and seeing whether N does or doesn't have those properties, like the Fermat Test above. If it doesn't, N is not prime. If it does, you cannot be sure. The fastest algorithms for very large numbers are also the most difficult to describe and use the most sophisticated mathematics. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.