## Re: [PrimeNumbers] testing if 32 bit integer is prime number

Expand Messages
• ... Tere Ylar, ... Think of 25... So you could add another check for divisibility by 5. Then think of 49. Hmmm, looks like you need to go a bit further... ...
Message 1 of 5 , Oct 2, 2001
On Tue, 02 October 2001, ylar.jyrviste@... wrote:
> Hi,

Tere Ylar,

> I need to show if a 32 bit integer is prime or not. Is it enough to
> prove that the number is greater than 2,odd number and divisible by 3?

Think of 25...
So you could add another check for divisibility by 5.
Then think of 49.
Hmmm, looks like you need to go a bit further...

> Or is there another simple algorithm to prove it(I hvae to implement
> it in assembler)

You have made the first few steps, the extension is to test all primes up to and including the square root of the number you want to test (equivalently - until p squared is larger than the number you're testing). For 32bit numbers this isn't too lengthy a process, but don't try it for larger numbers. The process is called 'wheel factoring', 'trial division', or simply 'brute force'.

Another question is how to generate all the primes easily.
There are two equally simple answers:
1) write a quick sieve to generate all primes up to 16-bits (which can be done really easily if you already know all primes up to 8-bits). See the Prime Pages for information on such a sieve:
http://www.utm.edu/research/primes/glossary/SieveOfEratosthenes.html

2) Don't bother - simply be prepared to be a bit wasteful with your tests.
Trial divide by 2 and 3 first, then after that trial divide by
6n-1 and 6n+1 for every n>=1 (so that's 5, 7, then 11, 13, then 17, 19, then 23, 25 (wasteful - already done 5) ...)
The above optimisation can be extended to
first do trial division by 2, 3, 5, 7, 11 and 13
then do trial division by 30n-13, 30n-11, 30n-7, 30n-1, 30n+1, 30n+7, 30n+11, 30n+13 for each n>=1.

Oh, and when I say 'every' or 'each' above, you are permitted to stop as soon as you find a factor!

http://www.frenchfries.net/paul/factoring/
but we're always here to answer questions too.

N�gemist,
Phil

Mathematics should not have to involve martyrdom;
Support Eric Weisstein, see http://mathworld.wolfram.com
Find the best deals on the web at AltaVista Shopping!
http://www.shopping.altavista.com
• ... You mean *not* divisible by 3, otherwise it certainly isn t prime. Even that s not good enough. Consider 25: odd, 2 and not divisible by 3. It s not
Message 2 of 5 , Oct 2, 2001
> I need to show if a 32 bit integer is prime or not. Is it enough to
> prove that the number is greater than 2,odd number and divisible by 3?

You mean *not* divisible by 3, otherwise it certainly isn't prime.

Even that's not good enough. Consider 25: odd, >2 and not divisible by
3. It's not prime either.

>
> Or is there another simple algorithm to prove it(I hvae to implement
> it in assembler)

There are many simple algorithms. Without knowing your constraints,
questions should guide you:

Can the input number be negative?
Although the input number may be 32 bits, are all 2^32 values possible?
Are you optimizing for speed, for data space, for program size, for
simplicity of programming or what?

If you have a lot of data storage, for instance, you could have a very
large table of primes and index into it to see whether a given value is
prime or not.

Paul
• May I suggest that you use strong pseudoprimes as described in http://www.utm.edu/research/primes/prove/prove2_3.html It may seem a bit more complex then the
Message 3 of 5 , Oct 2, 2001
May I suggest that you use strong pseudoprimes as described in
http://www.utm.edu/research/primes/prove/prove2_3.html
It may seem a bit more complex then the other methods, but requires almost
no storage space and shouldn't be TOO difficult to implement. Specifically,
you can use other people's work to reduce your workload by using bases 2, 7
and 61, which can verify a number to be prime if it is less than 4759123141
(more than 32 bits). Bitshifting can be used to take care of any necessary
divisions by two and the modulus and exponentiation algorithms won't be very
hard to implement in assembly (you would probably need a modulus or
equivalent function for trial divisions anyway). At the very least, it is
an interesting alternative to trial division.

Hope this helps,

James

James Thoms
3B Computer Engineering
University of Waterloo

From: ylar.jyrviste@...
Subject: [PrimeNumbers] testing if 32 bit integer is prime number
Date: Tue, 02 Oct 2001 11:58:19 -0000

Hi,

I need to show if a 32 bit integer is prime or not. Is it enough to
prove that the number is greater than 2,odd number and divisible by 3?

Or is there another simple algorithm to prove it(I hvae to implement
it in assembler)

Thanks

a computer science student

_________________________________________________________________
• ... Good suggestion. Ready-made source code, by Professor Caldwell, in JavaScript, can be found at
Message 4 of 5 , Oct 2, 2001
On Tue, 02 October 2001, "James Thoms" wrote:
> May I suggest that you use strong pseudoprimes as described in
> http://www.utm.edu/research/primes/prove/prove2_3.html
> It may seem a bit more complex then the other methods, but requires almost
> no storage space and shouldn't be TOO difficult to implement. Specifically,
> you can use other people's work to reduce your workload by using bases 2, 7
> and 61, which can verify a number to be prime if it is less than 4759123141
> (more than 32 bits). Bitshifting can be used to take care of any necessary
> divisions by two and the modulus and exponentiation algorithms won't be very
> hard to implement in assembly (you would probably need a modulus or
> equivalent function for trial divisions anyway). At the very least, it is
> an interesting alternative to trial division.

Good suggestion. Ready-made source code, by Professor Caldwell, in JavaScript, can be found at

http://primes.utm.edu/curios/includes/file.php/primetest.html

Phil

Mathematics should not have to involve martyrdom;
Support Eric Weisstein, see http://mathworld.wolfram.com
Find the best deals on the web at AltaVista Shopping!
http://www.shopping.altavista.com
Your message has been successfully submitted and would be delivered to recipients shortly.