The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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

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 

has a link to 100,000 primes, but this doesn't quite get as far as you
need.  The link 

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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.