Determining if a Large Number is Prime
Date: 05/05/2004 at 14:41:38 From: Jerry Subject: prime number? Is 333667 a prime? I have ruled out all evens plus 5, 10, 7, 8, 9, 13, 17, and 19 as possible factors but do not know how to proceed from there.
Date: 05/05/2004 at 15:03:17 From: Doctor Ian Subject: Re: prime number? Hi Jerry, Note that you only need to check prime factors. For example, for something to be divisible by 10, it would also have to be divisible by 2 and by 5, so having checked those, you don't need to check any of their products. Does that make sense? Second, you only need to check primes up to the square root of the number you're trying to factor. This is because if you have one factor larger than the square root, the other factor will have to be smaller, so you'll find it first. So you need to check all the primes smaller than sqrt(333667) < 578 That's still a lot of primes, though! So for numbers like this, which are big, but not _too_ big, the easiest thing to do is to check a table of prime numbers! Our prime number FAQ at Prime numbers http://mathforum.org/dr.math/faq/faq.prime.num.html has a link to 100,000 primes, but this doesn't quite get as far as you need. The link http://www.utm.edu/research/primes/lists/small/ has longer lists, and you will find your number in their list. If you have any questions about this or need more help, please write back and show us what you have been able to do, and we will try to offer further suggestions. - Doctor Vogler and Doctor Ian, 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.