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?

• jschnei: You might be interested in a similar review I did a while back; a lot of the algorithmic notes there also apply here: codereview.stackexchange.com/questions/165576/…

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

• Tamoghna Chowdhury: Just include <stdbool.h> to avoid having to define it yourself, and get the lowercase versions at the same time.
• rossum: @TamoghnaChowdhury: Thanks. My C is very rusty.

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.