Thread: Algorithm

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    164

    Algorithm

    Can some one tell me the algorithm or procedure of how to find prime numbers ??

    Note Im not asking that how to code it just asking the way of it.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    There are several algorithms. I quite like "Sieve of Eratosthenes" as a quite "neat" one.

    Almost all other algorithms follow this principle: Take a number, try to divide by the numbers 2, 3, 5, 7, .... until square-root of number. If you "generate" odd numbers, there is no reason to try to divide by 2, of course.

    The really naive approach is:
    Code:
    int is_prime(int n)
    {
        if(n % 2 == 0) return 0;
       for(i = 3; i *i  < n; i++) {
          if (n % i == 0) return 0;
       }
       return 1;
    }
    It improves performance quite a bit to only try prime-numbers - so don't divide by 9, 15. If it didn't divide by 3, it's not going to divide by 9. If it didn't divide by 5, it's not going to divide by 15. When numbers get a bit bigger, about 2 in 3 numbers are NOT primes.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    One thing you can do is keeping track of all prime numbers you find, and only testing against those. Repeated exact prime number testing is pretty much a trade-off between memory and speed.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> The really naive approach is:

    just for the sake of correctness, 1 is not a prime.

    >> Repeated exact prime number testing is pretty much a trade-off between memory and speed.

    which is why probabalistic and deterministic algorithms (such as Miller-Rabin and AKS) are more often used in practice, since they are efficient in both respects.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Sebastiani View Post
    >> The really naive approach is:

    just for the sake of correctness, 1 is not a prime.
    I'm sorry, but where does it say that 1 is a prime in my text?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I'm sorry, but where does it say that 1 is a prime in my text?
    It says so in your code (and your code also says that 2 is not prime), but then again, your code snippet was just an example not intended to work out of the box.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    well, the function you posted would report it as being so. also, numbers less than 1 are not generally not tested for primality.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by laserlight View Post
    It says so in your code (and your code also says that 2 is not prime), but then again, your code snippet was just an example not intended to work out of the box.
    Ah yes, now I get it. Yeah, my code is a bit broken in all sorts of ways. It also don't work for primes under 9, since it never enters the loop in that case - I was trying to be clever and check for the square-root in a different way, but it breaks the for-loop before it's entered, since ( 3 * 3 > n) is not true.

    And of course, it should check for exactly 2 and return 1.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM