
March 26th, 2002, 10:39 AM
#1
Prime number?
Could anybody tell me how mathamatically you would determinte if a number is prime (what is the formula)?
Thanks in advance.
If you don\'t learn the rules nobody can accuse of cheating.

March 26th, 2002, 11:10 AM
#2
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 n1 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?
"To estimate the time it takes to do a task, estimate the time you think it should take, multiply by two, and change the unit of measure to the next highest unit. Thus we allocate two days for a onehour task."  Westheimer's Rule

March 26th, 2002, 11:58 AM
#3
Link
The Prime Pages:
http://www.utm.edu/research/primes/
Everything you need to know about prime numbers (research, records, resources).
ZeroOne
Q: Why do computer scientists confuse Christmas and Halloween?
A: Because Oct 31 = Dec 25

March 26th, 2002, 12:24 PM
#4
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

March 26th, 2002, 12:24 PM
#5
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).
If you don\'t learn the rules nobody can accuse of cheating.

March 26th, 2002, 12:37 PM
#6
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
"To estimate the time it takes to do a task, estimate the time you think it should take, multiply by two, and change the unit of measure to the next highest unit. Thus we allocate two days for a onehour task."  Westheimer's Rule

March 26th, 2002, 12:58 PM
#7
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.
The COOKIE TUX lives!!!!
Windows NT crashed,I am the Blue Screen of Death.
No one hears your screams.

March 26th, 2002, 01:34 PM
#8
Thanks everybody. Problem solved.
I'm going to use the APR test that Brainstop mentioned (and came from ZeroOne's link).
Again thanks.
If you don\'t learn the rules nobody can accuse of cheating.

March 26th, 2002, 02:00 PM
#9
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.

March 26th, 2002, 02:06 PM
#10
Heh. You're right.
It'll make the run time 1/4 (inverse square law) of the original function, won't it?!
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

