Prime Number between given interval

Question

Given below is the code for finding prime numbers between the interval entered by the user.

#include <stdio.h>

int main() {
    int n1, n2, i, flag;
    scanf("%d%d", &n1, &n2);
    for (i = n1; i <= n2; i++) {
        flag = prime(i);
        
        if (flag == 1)
            printf("\n%d", i);
        
    }
    return 0;
}

int prime(int n) {
    int j, flag = 1;
    for (j = 2; j <= n / 2; j++) {
        if (n % j == 0) {
            flag = 0;
            break;
        }
    }
    return flag;
}

Can anyone explain me how this code deals with odd number, which are not prime (for ex: 15, 21, 25, etc)

int prime(int n) {
    int j, flag = 1;
    for (j = 2; j <= n / 2; j++) {
        if (n % j == 0) {
            flag = 0;
            break;
        }
    }
    return flag;
}

See in this prime function, when we observe the iteration of for loop if value of n is 15 then it will look like this:

for (j = 2; j <= 15 / 2; j++)  

I agree this is true. Because 2<7. Since the condition is true we will enter inside the for loop:

    if(n%j==0){
        flag=0;
        break;
    }

Now, since n=15 and j=2, value of n%j=1, which is obviously not equals to 0; so if loop will not be executed and the prime function will return flag =1; and the main function will print 15 as a prime.

But, after Executing the program the code is showing the correct results: it's not showing 15 as a prime.

So can anyone please help me understand the logic behind this code? (Actually I want to understand how this code is eliminating non-prime odd numbers.)

Answer 1

You checked the execution for j==2, but since there is a for loop for(j=2;j<=n/2;j++). The code will run from j=2 to j=n/2. So, if you consider all the iterations, you will realize that the function is working fine.

1. The first if statement is false, so for j==2, the program won't go inside the if statement.
2. The loop will iterate for the next value of j, which is 3. Since 15%3 == 0, the program will execute the statements within the if statement and return that 15 is not a prime number.

    for(j=2;j<=n/2;j++){
        if(n%j==0){
            flag=0;
            break;
        }
    }

Answer 2

In the case of n=15, the loop starts at i=2, the test i<=n/2 is true because 2<=7, then 15%2 is 1, hence the loop proceeds and i is incremented to 3, the loop test is true again because 3<=7 but 15%3 is 0 so flag is set to 0 and returned.

Note these remarks:

• the code does not have a recursive function. You merely call a function prime() to check each number in the interval for primality.
• prime() should be defined or at least declared before the main() function that calls it.
• you can test the return value of prime(i) directly. No need for a flag variable.
• for prime numbers, the loop will iterate way too far: you can change the test to j <= n / j to stop at the square root of n.
• you can return directly from the loop body.
• you should output the newline after the number.

Here is a modified version:

#include <stdio.h>

int isprime(int n) {
    int j;
    for (j = 2; j <= n / j; j++) {
        if (n % j == 0)
            return 0;
    }
    return 1;
}

int main() {
    int n1, n2, i;

    if (scanf("%d%d", &n1, &n2) != 2)
        return 1;
    for (i = n1; i <= n2; i++) {
        if (isprime(i))
            printf("%d\n", i);
    }
    return 0;
}

Answer 3

Can anyone explain me how this code deals with odd number, which are not prime (for ex: 15, 21, 25, etc)

int prime(int n) {
    int j, flag = 1;
    for (j = 2; j <= n / 2; j++) {
        if (n % j == 0) {
            flag = 0;
            break;
        }
    }
    return flag;
}

Well this function doesn't need to handle specially nonprime numbers, based on the fact that if we can divide the number n by something (be prime or not), the number will be compose. What it does it to get out of the loop (with flag changed into 0) as soon as it finds a number j that divides n.

There's an extra optimization, that can save you a lot of time, that consists on calculating numbers until the integer rounded down square root of n as, if you can divide the number by a number that is greater than the square root, for sure there will be a number that is less than the square root that also divides n (the result of dividing the original number by the first will give you a number that is lower than the square root) so you only need to go up until the square root. While calculating the square root can be tedious (there's a library function, but let's go on), it is only done once, so it is a good point to use it. Also, you can initialy try dividing the number by two, and then skip all the even numbers, by adding 2 to j, instead of incrementing.

#include <math.h>

/* ... */

int prime(unsigned n) {
    /* check for special cases */
    if (n >= 1 && n <= 3) return TRUE; /* all these numbers are prime */
    if (n % 2 == 0) return FALSE; /* all these numbers are not */
    /* calculate (only once) the rounded down integer square root */
    int j, square_root = isqrt(n); /* see below */
    for (j = 3; j <= square_root; j += 2) { /* go two by two */
        if (n % j == 0)
            return FALSE;
    }
    /* if we reach here, all tests failed, so the number must be prime */
    return TRUE;
}

While there's a sqrt() function in <math.h>, I recommend you to write an integer version of the square root routine (you can devise it easily) so you don't need to calculate it in full precision (just to integer precision).

/* the idea of this algorithm is that we have two numbers between 1 and n,
 * the greater being the arithmetic mean between the previous two, while
 * the lower is the result of dividing the original n by the arithmetic mean.
 * it is sure than if we select the arithmetic mean, the number will be
 * between the previous ones, and if I divide n by a number that is lower,
 * the quotient will be higher than the original number.  By the way, the
 * arithmetic mean is always bigger than the square root, so the quotient
 * will be smaller.  At each step, both numbers are closer to each other, and
 * so, the smaller is closer to the result of dividing n by itself (and this
 * is the square root!)
 */
unsigned isqrt(unsigned n)
{
    unsigned geom = 1, arith = n;
    while (geom < arith) {
        arith = (geom + arith) / 2;
        geom = n / arith;
    }
    /* return the smaller of the two */
    return arith;
}

so, your program would be:

#include <stdio.h>

#define FALSE (0)
#define TRUE (!FALSE)

unsigned isqrt(unsigned n)
{
    unsigned geom = 1, arith = n;
    while (geom < arith) {
        arith = (geom + arith) / 2;
        geom = n / arith;
    }
    return arith;
}

int prime(unsigned n) {
    /* check for special cases */
    if (n >= 1 && n <= 3) return TRUE;
    if (n % 2 == 0) return FALSE;
    /* calculate (only once) the rounded down integer square root */
    int j, square_root = isqrt(n);
    for (j = 3; j <= square_root; j += 2) {
        if (n % j == 0) {
            return FALSE;
        }
    }
    return TRUE;
}

int main() {
    unsigned n1, n2, i;

    scanf("%u%u", &n1, &n2);

    for (i = n1; i <= n2; i++) {
        if (prime(i))
            printf("%u\n", i);

    }
    return 0;
}

If you try your version against this one, with values like 2000000000 and 2000000100 you will see how this is saving a lot of calculations (indeed, for the cases below, the case of considering only the odd numbers when going throug the loop will take out of it half the numbers ---this is 1000000000 tests---, but the square root will reduce the number of tests to its square root ---only around 40000 tests--- for each number!!!).

$ primes
2000000000 2000000100 
2000000011
2000000033
2000000063
2000000087
2000000089
2000000099
$ _

Your version takes (on my system) this execution time:

$ echo 2000000000 2000100000 | time primes0 >/dev/null
3.09user 0.00system 0:03.09elapsed 99%CPU (0avgtext+0avgdata 1468maxresident)k
0inputs+0outputs (0major+69minor)pagefaults 0swaps
$ _

while the version proposed takes:

$ echo 2000000000 2000100000 | time primes >/dev/null
0.78user 0.00system 0:00.78elapsed 99%CPU (0avgtext+0avgdata 1572maxresident)k
0inputs+0outputs (0major+72minor)pagefaults 0swaps
$ _