c - 为什么质数检查对大数会得到错误的结果？

Question

这个小型 C 脚本检查数字是否为质数...不幸的是它不能完全工作。我知道脚本效率低下(例如 sqrt 优化)，这些都不是问题。

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

我用很多数字测试了这个程序并且它有效......然后我尝试了一个更大的数字(1231231231231236)这显然不是质数......但是:程序告诉我它是!？

我错过了什么......？

Answer 1

数字“1231231231231236”太大，不适合“int”数据类型。添加一个 printf 语句来显示您的程序认为您给了它多少数字，如果它是质数，您的程序就可以正常工作；否则，您可能有一个值得检查的问题。添加对任意大小整数的支持需要付出相当多的额外努力。

您遇到此问题的原因是像 int 这样的内部数据类型具有固定大小 - 对于 int 可能是 32 位或 4 字节。鉴于此，int 类型的变量只能表示 2^32 个唯一值——大约 40 亿。即使您使用的是 unsigned int(您不是)，int 类型也不能用于存储大于 40 亿左右的数字。您的数字比那个大几个数量级，因此，当您尝试将输入放入 int 变量时，会发生一些事情，但我可以告诉您没有发生什么:它没有被分配值 1231231231231236 .