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

---

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.

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.

Quote:

---

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

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.

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

Quote:

---

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?

Quote:

---

Originally Posted by laserlight

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

---

Thanks.

Quote:

---

Originally Posted by jjohan

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.

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

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

Quote:

---

Originally Posted by jjohan

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.

Sieve of Eratosthenes - Wikipedia, the free encyclopedia