Thread: 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;
}

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;
}

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)

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.

OP, try reading this : Primality test - Wikipedia, the free encyclopedia and see if you can understand it.

Originally Posted by jjohan

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).

Originally Posted by laserlight

Test to measure and find out. anduril462 has mentioned something about this in post #7.

Yeah I'm just starting to look into Gprof.

Originally Posted by laserlight

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?

Originally Posted by laserlight

Probably because you made parts of the code appear in a bold font.

Thanks.

Ah, ok. I then go up until sqrt(n). Thanks again.