CODEWITHSUNDEEP
cprimes
janniks
janniks

Reputation: 3180

Why is prime number check getting wrong results for large numbers?

This small C script checks if a number is a prime... Unfortunately it doesn't fully work. I am aware of the inefficiency of the script (e.g. sqrt optimization), these are not the problem.

#include <stdio.h>

int main() {
  int n, m;

  printf("Enter an integer, that will be checked:\n"); // Set 'n' from commandline
  scanf("%d", &n); // Set 'n' from commandline

  //n = 5; // To specify 'n' inside code.

  for (m = n-1; m >= 1; m--) {
    if (m == 1) {
      printf("The entered integer IS a prime.\n");
      break;
    }
    if (n % m == 0) {
      printf("The entered integer IS NOT a prime.\n");
      break;
    }
  }
  return 0;
}

I tested the programm with a lot of numbers and it worked... Then I tried a bigger number (1231231231231236) which is clearly not a prime... BUT: the program told me it was!?

What am I missing...?

Upvotes: 2

Views: 293

Answers (3)

Yogesh P
Yogesh P

Reputation: 321

The given number is too large for integer in C. Probably it only accepted a part of it. Try Printing the value of n.

Upvotes: 1

ddodev
ddodev

Reputation: 131

Hard to know without more details, but if your ints are 32-bit, then the value you've passed is outside the allowable range, which will no doubt be represented as something other than the value you've passed. You may want to consider using unsigned int instead.

Upvotes: 1

Patrick87
Patrick87

Reputation: 28302

The number "1231231231231236" is too big to fit in an "int" data type. Add a printf statement to show what number your program thinks you gave it, and if that's prime, your program works fine; else, you might have a problem that merits checking. Adding support for integers of arbitary size requires considerable extra effort.

The reason you are having this problem is that intrinsic data types like int have a fixed size - probably 32 bits, or 4 bytes, for int. Given that, variables of type int can only represent 2^32 unique values - about 4 billion. Even if you were using unsigned int (you're not), the int type couldn't be used to store numbers bigger than around 4 billion. Your number is several orders of magnitude larger than that and, as such, when you try to put your input into the int variable, something happens, but I can tell you what doesn't happen: it doesn't get assigned the value 1231231231231236.

Upvotes: 6

Related Questions