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

Think of 25...

> prove that the number is greater than 2,odd number and divisible by 3?

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

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

> it in assembler)

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!

There's more info about factoring, and some sample code at

http://www.frenchfries.net/paul/factoring/

There's more info about primality proving in general on the Prime Pages http://primepages.org/

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 > I need to show if a 32 bit integer is prime or not. Is it enough to

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

> prove that the number is greater than 2,odd number and divisible by 3?

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

3. It's not prime either.

>

There are many simple algorithms. Without knowing your constraints,

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

> it in assembler)

it's hard to give definite advice. The answers to the following

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

To: primenumbers@yahoogroups.com

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

_________________________________________________________________

Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp - On Tue, 02 October 2001, "James Thoms" wrote:
> May I suggest that you use strong pseudoprimes as described in

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

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

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