Could anybody tell me how mathamatically you would determinte if a number is prime (what is the formula)?
Thanks in advance.
Printable View
Could anybody tell me how mathamatically you would determinte if a number is prime (what is the formula)?
Thanks in advance.
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?
The Prime Pages:
http://www.utm.edu/research/primes/
Everything you need to know about prime numbers (research, records, resources). :)
-ZeroOne :cool:
I think this is right, but my coding is a little rusty to say the least...
Code: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
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).
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
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.
Thanks everybody. Problem solved.
I'm going to use the APR test that Brainstop mentioned (and came from ZeroOne's link).
Again thanks. :D
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.
Heh. You're right.
It'll make the run time 1/4 (inverse square law) of the original function, won't it?!
Ah, The Sieve of Eratosthenes. I wrote some on it a while back if anyone is interested:
http://www.cshrp.net/content.aspx?showID=612
Rewandythal> also do b+2 instead of b++. If 2 is eleminated, then no even number can possible go into a.
garathjax> I don't remember exactly which test the ARP test is....and don't have time to look it up right now. I just wanted to warn you that certain tests only work for certain primes. Certain numbers (2^3-1 for example) follow set rules, but that doesnt mean that all primes follow the same rules. Some just make it quick to find. There is a project called the GIMP (I believe) which is working on determining extreamly large prime numbers. The last one was something like 4million digits. Their goal is to find the first prime number greater then 10million digits.
b=2, b+2 takes is straight to 4, missing out 3, I'd have to go from b=1, which would return 1 and would *appear* therefore not to be prime (since a / 1 would be a whole number).
I could of course start at 3, but it'd then miss out the important /2 stage, so 4, for example, would be misreported as prime.
This solves the problem, by checking for divisible by 2 first, then starting at 3, incrementing in 2's (all the odd numbers).Code:int IsPrime(int a)
{
int b;
int c;
if( (a div 2) == (a / 2))
{
c = 1;
}
for(b = 3;b < sqrt(a); b + 2)
{
if( (a div b) == (a / b))
{
c = 1;
}
}
return c;
}
// Returns 0 if prime, 1 if not