3
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Just include <stdbool.h> to avoid having to define it yourself, and get the lowercase versions at the same time. \$\endgroup\$ – Tamoghna Chowdhury Jul 10 '17 at 5:13
  • \$\begingroup\$ @TamoghnaChowdhury: Thanks. My C is very rusty. \$\endgroup\$ – rossum Jul 10 '17 at 7:49
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.