Prime number?
Page 1 of 2 12 LastLast
Results 1 to 10 of 14

Thread: Prime number?

  1. #1
    Senior Member
    Join Date
    Feb 2002
    Posts
    133

    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.

  2. #2
    Senior Member BrainStop's Avatar
    Join Date
    Jan 2002
    Posts
    295
    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?
    "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 one-hour task." -- Westheimer's Rule

  3. #3
    Senior Member
    Join Date
    Oct 2001
    Location
    Helsinki, Finland
    Posts
    570

    Lightbulb 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

  4. #4
    Senior Member
    Join Date
    Oct 2001
    Posts
    677

    Lightbulb

    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
    One Ring to rule them all, One Ring to find them.
    One Ring to bring them all and in the darkness bind them.
    (The Lord Of The Rings)
    http://www.bytekill.net

  5. #5
    Senior Member
    Join Date
    Feb 2002
    Posts
    133
    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.

  6. #6
    Senior Member BrainStop's Avatar
    Join Date
    Jan 2002
    Posts
    295
    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 one-hour task." -- Westheimer's Rule

  7. #7
    Senior Member
    Join Date
    Jan 2002
    Posts
    883
    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.


  8. #8
    Senior Member
    Join Date
    Feb 2002
    Posts
    133
    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.

  9. #9
    Senior Member
    Join Date
    Mar 2002
    Posts
    425
    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.

  10. #10
    Senior Member
    Join Date
    Oct 2001
    Posts
    677
    Heh. You're right.
    It'll make the run time 1/4 (inverse square law) of the original function, won't it?!
    One Ring to rule them all, One Ring to find them.
    One Ring to bring them all and in the darkness bind them.
    (The Lord Of The Rings)
    http://www.bytekill.net

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

 Security News

     Patches

       Security Trends

         How-To

           Buying Guides