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/