Associated Topics || Dr. Math Home || Search Dr. Math

### 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

http://www.utm.edu/research/primes/lists/small/

has longer lists, and you will find your number in their list.

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/
```
Associated Topics:
Elementary Prime Numbers
Middle School Prime Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search