Prime number generator in C

Question

I have to print numbers between two limits n and m, t times.

I created t variable that stores a number of test cases.

Outer for loop iterates for every test cases.

Inner for loop prints primes from m to n.

Code

#include <stdio.h>
#include <stdlib.h>
 
int is_prime(int);
 
int main(void) {
    int t, m, n;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        scanf("%d %d", &m, &n);
        for (int j = m; j <= n; j++) {
            if (is_prime(j)) {
                printf("%d\n", j);
            }
        }
        if (i < t - 1) printf("\n");
    }
 
    return 0;
}
 
int is_prime(int num) {
    if (num <= 1) return 0;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}

Problem: http://www.spoj.com/problems/PRIME1/

Can I have review?

Answer 1

The only even prime number is two, so with a little extra coding you can ignore even numbers in the for loop. For even more speed use a sieve, though maybe save that for when you get a 'TLE' failure.

A more formal code layout would be good as well, your if statements need expanding to include {...}. More vertical space (blank lines) a well as explanatory comments help. When you come back to your old code six months later you will thank yourself.

I prefer to set 0 and 1 as FALSE and TRUE to make code easier to read YMMV.

int is_prime(int num) {
  if (num <= 1) {
    return FALSE;
  }

  // Even numbers.
  if (num % 2 == 0) {
    return num == 2;  // 2 is the only even prime.
  }

  // Odd numbers.
  // Start loop at 3 and step 2 to skip even divisors.
  for (int i = 3; i * i <= num; i += 2) {
    if (num % i == 0) {
        return FALSE;
    }
  }
  return TRUE;
}

Answer 2

Good that OP's code handles values <= 0, yet could have used is_prime(unsigned num) instead. Further: this is a good place for the only even prime detect.

Corner concern: The i * i <= num test fails for large num, like num = INT_MAX as i*i is always <= than INT_MAX or it is int overflow - which is undefined behavior (UB).

Preference: Use bool for return values that are either 0 or 1.

Many modern compilers/processors calculate the remainder and quotient for little/no additional cost. Use that as an exit condition.

bool is_prime(uintmax_t num) {
  if (num <= 3) {
    return num >= 2;
  }
  uintmax_t q = num;
  for (uintmax_t i = 3; i <= q; i += 2) {
    if (num % i == 0) {
      return false;
    }
    q = num / i;
  }
  return num%2;
}

The next step in prime detection is use of the Sieve of Eratosthenes

---

Note for future: Code does not check the return value of scanf(). This is OK for test code, but not for code under test.