finding prime numbers between a range in C

Question

I am trying to find the prime numbers in a range using C language. My code does not give an output and I think there is a logical error here which I cannot figure out. Can anyone please help?

#include <stdio.h>

int main() {
    int lowerLevel;
    int upperLevel;
    int i; //counter variable
    int prime = 0;
    int flag = 0;
    printf("Enter the lower limit and upper limit of the range followed by a comma :");
    scanf("%d %d", &lowerLevel, &upperLevel);

    for (i = 2; i <= upperLevel; ++i) {
        if (i % 2 == 0) {
            flag = 1;
            break;
        }
    }
    if (flag == 0) {
        printf("%d", i);
        ++i;
    }

    return 0;
}

Answer 1

Let's follow the logic of your code:

#include <stdio.h>
#include <string.h>

int main() {
    int lowerLevel;
    int upperLevel;
    int i; //counter variable
    int prime = 0;
    int flag = 0;
    printf("Enter the lower limit and upper limit of the range followed by a comma :");
    scanf("%d %d", &lowerLevel, &upperLevel);

    for (i = 2; i <= upperLevel; ++i) {
        if (i % 2 == 0) {
            flag = 1;
            break;
        }
    }
    if (flag == 0) {
        printf("%d", i);
        ++i;
    }

    return 0;
}

First of all, you have a loop:

    for (i = 2; i <= upperLevel; ++i) {
        if (i % 2 == 0) {
            flag = 1;
            break;
        }
    }

this loop tries to find a number i that is a multple of 2, because as soon you get one, you jump out of the loop. So your loop can be expressed better as:

    for (i = 2; i <= upperLevel && i % 2 != 0; ++i) {
    }
    /* i > upperLevel || i % 2 == 0 */
    if (i <= upperLevel && i % 2 == 0) {
        flag = 1;
    }

We still need to check if i <= upperLevel && i % 2 == 0 to set the variable flag = 1 if we exited the loop because i was a multiple of 2, but the break; is not necessary because we are already out of the loop.

Now let's check that the first value we initialize i is, indeed 2 (which is a multiple of 2) and the consecuence of this is that the loop is never going to be entered. Se we can eliminate it completely, giving to:

    i = 2;
    if (i <= upperLevel && i % 2 == 0) {
        flag = 1;
    }

now, the second clause of the if test is always true, so we can take it off, giving:

    i = 2;
    if (i <= upperLevel) {
        flag = 1;
    }

Now, let's append the second part:

    i = 2;
    if (i <= upperLevel) {
        flag = 1;
    }
    if (flag == 0) {
        printf("%d", i);
        ++i;
    }
    return 0;

so, the first thing we see here is that your ++i; statement is nonsense, as it is the last statement to be executed before exiting the program, so we can also take it off.

    i = 2;
    if (i <= upperLevel) {
        flag = 1;
    }
    if (flag == 0) {
        printf("%d", i);
    }
    return 0;

Now we see that you print the value of i only if the value of flag is zero, but flag only conserves its zero value if the value of i > upperLevel, and as i is fixed, the printing of i only occurs if you input a value of upperlevel that is less than 2.

We can rewrite the above code as this:

    if (2 > upperLevel) {
        printf("%d", 2);
    }

Your program will print 2 only if you provide a value of upperLevel less than 2.

Answer 2

Optimal method with Sieves of Eratosthenes

You should use the sieves of Eratostenes algorithm, it is way more efficient to get the different prime number.

it does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2

Basically you consider all numbers prime by default, and then you will set as false the prime number, see below code:

#include <stdio.h>

/// unsigned char saves space compared to integer
#define bool    unsigned char
#define true    1
#define false   0
// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
void printPrimesRange(int lowerLevel, int n) {
    if (lowerLevel < 0 || n < lowerLevel) // handle misused of function
        return ;
    bool isPrime[n + 1];
    memset(isPrime, true, n + 1);
    int cnt = 0; // NB: I use the counter only for the commas and final .\n, its optional.

    if (lowerLevel <= 2 && n >= 2) { // only one even number can be prime: 2
        ++cnt;
        printf("2");
    }
    for (int i = 3; i <= n ; i+=2) { // after what only odd numbers can be prime numbers
        if (isPrime[i]) {
            if (i >= lowerLevel) {
                if (cnt++)
                    printf(", ");
                printf("%d", i); // NB: it is better to print all at once if you can improve it
            }
            for (int j = i * 3; j <= n; j+=i*2) // Eratosthenes' Algo, sieve all multiples of current prime, skipping even numbers
                isPrime[j] = false;
        }
    }
    printf(".\n");
}

int main(void) {
    int lowerLevel;
    int upperLevel;

    printf("Enter the lower limit and upper limit of the range with a space in-between:"); // space, not comma
    scanf("%d %d", &lowerLevel, &upperLevel);
    printPrimesRange(lowerLevel, upperLevel);
    return 0;
}

Answer 3

Your code does not check for prime numbers, it merely checks that there is at least one even number between 2 and upperlevel, which is true as soon as upperlevel >= 2. If there is such an even number, nothing is printed.

You should instead run a loop from lowerlevel to upperlevel and check if each number is a prime and if so, print it.

Here is a modified version:

#include <stdio.h>

int main() {
    int lowerLevel, upperLevel;

    printf("Enter the lower limit and upper limit of the range: ");
    if (scanf("%d %d", &lowerLevel, &upperLevel) != 2) {
        return 1;
    }
    for (int i = lowerLevel; i <= upperLevel; ++i) {
        int isprime = 1;
        for (int p = 2; p <= i / p; p += (p & 1) + 1) {
            if (i % p == 0) {
                isprime = 0;
                break;
            }
        }
        if (isprime) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

This method is simplistic but achieves the goal. More efficient programs would use a sieve to find all prime numbers in the range without costly divisions.