Thread: Challenge (prime numbers): Can you write a program more efficient than mine?

  1. #1
    Registered User
    Join Date
    Sep 2014
    Posts
    83

    Challenge (prime numbers): Can you write a program more efficient than mine?

    Hi,

    I just made a program that takes an integer as input and then prints out all prime numbers less than or equal to this integer. Below is the code.
    Are you able to rewrite this code so it becomes more efficient?

    Code:
    // Prints out all prime numbers between 1 and n, including n.
    // A prime number can only be divided by 1 and itself. 1 is not a prime number, lowest is 2.
    
    #include <stdio.h>
    
    
    int prime(int n)        // Investigates if a number is a prime number, returns 1 if true, 0 if false
    {
        int i, dividable;
        
        dividable = 0;
        if(n == 1)
            dividable = 1;
        
        for(i = 2; i < n; i++)
        {
            if(n%i == 0)
                dividable = 1;
        }
        
        if(dividable == 1)
            return 0;
        else 
            return 1;
    }
    
    
    int main(void)
    {
        int n, true_or_false ,i;
        
        printf("Highest number: ");
        scanf("%d", &n);
        printf("Prime numbers between 1 and %d:\n", n);
        
        for(i = 1; i <= n; i++)
        {
            true_or_false = prime(i);
            if(true_or_false == 1)
                printf("%d\n", i);
            else;
        }
            
        return 0;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,341
    You can read up about alternative algorithms for obtaining a list of primes. In your program though, the simplest speed up that I can see would be to skip primality testing of even numbers greater than 2.
    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

  3. #3
    Registered User
    Join Date
    Sep 2014
    Posts
    83
    Aha, like this I guess (changed the bold part):

    Code:
    int main(void)
    {
        int n, true_or_false ,i;
        
        printf("Highest number: ");
        scanf("%d", &n);
        printf("Prime numbers between 1 and %d:\n", n);
        
        for(i = 1; i <= n; i++)
        {
            if((i%2) != 0 || (i == 2))
            {
                true_or_false = prime(i);
                if(true_or_false == 1)
                    printf("%d\n", i);
                else;
            }
        }
            
        return 0;
    }

  4. #4
    Registered User
    Join Date
    Sep 2014
    Posts
    83
    By the way. Does anyone know a way how to test how efficient the above 2 versions are compared to each other?
    (Like for example if theres a way to show the calculation time for both if let's say n = 100)

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    First, a note on accuracy: 0 and 1 are neither prime nor composite. Thus, having 1 in your main loop, and having a special condition for it in your prime() function, is pointless. This implies that the user should only enter values for n >= 2, or if they enter 0 or 1, you can skip the whole thing and just print out "No primes in the range you specified" or some such.

    You can simply list 2 explicitly (it's the only even prime) and start your main loop at 3. You can change your loop increment (i++) to avoid the whole i %2 bit -- the divide (/) and modulus (%) operators are typically the slowest of the arithmetic operations -- but I'll let you figure out the correct increment statement.

    Also, in your prime function, your loop doesn't need to go all the way to n, you can stop before that. See if you can figure out what the lowest number you need to check is.

    Lastly, as soon as you know the number is not prime, you should bail out. If it's divisible by 3, no need to check if it's divisible by 4, 5, 6, 7, 8, etc. You know it's not prime.

  6. #6
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    OP, try reading this : Primality test - Wikipedia, the free encyclopedia and see if you can understand it.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by jjohan View Post
    By the way. Does anyone know a way how to test how efficient the above 2 versions are compared to each other?
    (Like for example if theres a way to show the calculation time for both if let's say n = 100)
    That depends on your OS. Google for "code profiling tools" is one way. Also, you can use some OS-specific time libraries if need be, and Linux offers the time command (though this is not always the best way).

  8. #8
    Registered User
    Join Date
    Sep 2014
    Posts
    83
    Thank you all!

    Here's my new code taking Andurils advice:
    Bolds indicates a change.

    Code:
    // More efficient than prime.c
    
    // Prints out all prime numbers between 1 and n, including n.
    // A prime number can only be divided by 1 and itself. 1 is not a prime number, lowest is 2.
    
    #include <stdio.h>
    
    
    int prime(int n)        // Investigates if a number >= 3 is a prime number, returns 1 if true, 0 if false
    {
        int i, dividable;
        
        dividable = 0;    
        
        
        for(i = 3; i <= (n / 2); i = i + 2)        // No need to go further than n/2
        {
            if(n%i == 0)
            {
                printf("Testing if %d dividable by %d\n", n, i);
                dividable = 1;
                break;
            }
        }
        
        if(dividable == 1)
            return 0;
        else 
            return 1;
    }
    
    
    int main(void)
    {
        int n, true_or_false ,i;
        
        
        printf("Highest number: ");
        scanf("%d", &n);
        printf("Prime numbers between 1 and %d:\n", n);
        
        if(n < 2) 
            printf("No prime numbers in the range\n");
        if(n >= 2)
            printf("2\n");
        
        for(i = 3; i <= n; i = i + 2)
        {
                true_or_false = prime(i);
                if(true_or_false == 1)
                    printf("%d\n", i);
                else;
        }
            
        return 0;
    }
    Hope this is more efficient than the last example.
    Hm I wonder why the code above doesn't appear as colourful as in my first post.
    Last edited by jjohan; 09-20-2014 at 02:16 AM.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,341
    Quote Originally Posted by jjohan
    Hope this is more efficient than the last example.
    Test to measure and find out. anduril462 has mentioned something about this in post #7.

    Note that "No need to go further than n/2" is true, but it states an upper bound on potential divisors that is still higher than necessary.

    Quote Originally Posted by jjohan
    Hm I wonder why the code above doesn't appear as colourful as in my first post.
    Probably because you made parts of the code appear in a bold font.
    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

  10. #10
    Registered User
    Join Date
    Sep 2014
    Posts
    83
    Quote Originally Posted by laserlight View Post
    Test to measure and find out. anduril462 has mentioned something about this in post #7.
    Yeah I'm just starting to look into Gprof.

    Quote Originally Posted by laserlight View Post
    Note that "No need to go further than n/2" is true, but it states an upper bound on potential divisors that is still higher than necessary.
    Hm ok interesting. So I can limit the loop even more than up until n/2 then?
    Quote Originally Posted by laserlight View Post
    Probably because you made parts of the code appear in a bold font.
    Thanks.

  11. #11
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by jjohan View Post
    Hm ok interesting. So I can limit the loop even more than up until n/2 then?
    If n is composite, then at least one of its factors squared will be less than or equal to n.

    Hint: This is easy to exploit, but avoid the beginners trap of using floating point. It can be exploited by working only with integral types.
    Last edited by grumpy; 09-20-2014 at 02:55 AM.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,341
    Quote Originally Posted by jjohan
    So I can limit the loop even more than up until n/2 then?
    Yes. Consider 17: if you do a trial division with 4, you end up with a quotient that is not less than 4 (4 itself, with integer division). If you do a trial division with 5, you end up with a quotient that is less than 5. As such, why would you need to go further with trial divisions past 5? There cannot be a factor of 17 greater than 5 that would not have already been found. In fact, since the quotient when dividing by 4 is less than 5, you would not even need to check with 5 since surely 5 would not be a factor.

    Furthermore, since you are listing those primes between 1 and n, you could cache the primes found (at least those that lie within the upper bound for n). This way, instead of just testing with odd numbers (including composite numbers), you can do perfect trial division by testing with the primes cached (until the upper bound for the number in question).
    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

  13. #13
    Registered User
    Join Date
    Sep 2014
    Posts
    83
    Ah, ok. I then go up until sqrt(n). Thanks again.

  14. #14
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by jjohan View Post
    Ah, ok. I then go up until sqrt(n).
    Yes, but note my previous comment about not using floating point (sqrt() is a floating point function). Look up "integer square root" instead.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  15. #15
    Registered User zub's Avatar
    Join Date
    May 2014
    Location
    Russia
    Posts
    104
    Our goals are clear, tasks are defined! Let's work, comrades! -- Nikita Khrushchev

Popular pages Recent additions subscribe to a feed