Prime number?

[garathjax]

Could anybody tell me how mathamatically you would determinte if a number is prime (what is the formula)?

Thanks in advance.

[BrainStop]

Well, you just try to divide the number by all numbers smaller than it except 1. If none of these numbers can divide the number without leaving a remainder, it's prime.

j = 0
for i = 2 to n-1 do
{
if (n div i) = (n / i)
then j = 1
}
if j = 1 then the number is not prime
else it is

Or something to that effect ....

Cheers,

BrainStop

PS = Just out of curiosity ... how is this security related?

[ZeroOne]

The Prime Pages:
http://www.utm.edu/research/primes/
Everything you need to know about prime numbers (research, records, resources).

-ZeroOne

[Rewandythal]

I think this is right, but my coding is a little rusty to say the least...

int IsPrime(int a)
{
	int b;
	int c;
	for( b = 2; b < a; b++) 
	{ 
		if( ( a div b) == ( a / b))
		{
			c = 1;
		}
	}
	return c;
}

// Returns 0 if prime, 1 if not

[garathjax]

Brainstop, as far as I know there is a much more efficient formula to do the job, I've seen it before but I can't remember where and I couldn't even find with google, and I was hoping somebody here knew what it is.
I'll use a formula the same or similar to the one you gave as a last resort if I have to but it'll quadruple the run time of the program (I need to test very large numbers).
Thanks anyway.


P.s. this question is only very loosely security related. I'm debugging an encryption program at the moment
(<-----mood) and I've found that it continuely crashes if it encounters a very large prime number (>10 to power of 18) which is randomly generated(I'm still not sure why, just that it does) so I want to write a function so that such a number will be rejected and a new number is generated (I know it's just a quick fix but I didn't originally write the program so I don't care).

[BrainStop]

Garathjax,

I did some quick searching and checked out ZeroOne's link ... if you hadn't gone through it already, the APR test and its variations seem to be the best method.

http://www.utm.edu/research/primes/prove/prove4_1.html

One webpage I found called the APR the world record holder in terms of speed.

Cheers,

BrainStop

[{P²P}Apocalypse]

Consider the list of integers 1 throuh n. Now consider the list of the first x primes {2,3,5,7,11,13, (list goes on with no predictable pattern)}

Divide all numbers (1 to n) by 2 and remove all that are divisible. This removes all evens.

Divide all remaining numbers by three and remove those divisible by 3.. The first one knocked out is 9.

Divide all remain by 5 and remove those divisible. The first one knocked out is 5 squared or 25.

Continue this procedure until the known list of primes has been exhaused. The first number remaining in the original list 1 through n is a prime.


Example: suppose I wish to determine all primes from 1 to 100 and I begin with the list of known primes {2,3,5,7}.

Divide the list 1,2,3,4,5,... by two and remove multiples of 2. The new list is 1,3,5,...

Divide by 3 and remove multiples. First one out is 9. New list is 5, 7, 11, and so on.

Divide by 5. Since 25 will be the first one knocked out of the list, those less than 25 are prime. The list of primes is now extented to {2,3,5,7,11,13,17,19}

This process can be continued indefinitely. The number of primes is infinite, but there is no formula or procedure for finding all of them. I am sure there are more efficient methods of determining whether a number is prime; however, I am not aware of such methods.

[garathjax]

Thanks everybody. Problem solved.
I'm going to use the APR test that Brainstop mentioned (and came from ZeroOne's link).
Again thanks.

[str34m3r]

I suppose now that garathjax has found his answer, this reply is moot, but I had a slight modification to Rewandythal's code. When I was in school, I wrote almost the exact same function for a program I was working for. The teacher actually made fun of me in front of the class for not realizing that I could have made it significantly shorter by only checking up to the square root of the number. Things like that just kind of stick with you.

Instead of :
>> for( b = 2; b < a; b++)
use:
for( b = 2; b < sqrt(a); b++)
and you'll save yourself some time.

[Rewandythal]

Heh. You're right.
It'll make the run time 1/4 (inverse square law) of the original function, won't it?!