Почему проверка простых чисел дает неправильные результаты для больших чисел?

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, имеют фиксированный размер - вероятно, 32 бита или 4 байта для int. Учитывая это, переменные типа int могут представлять только 2 ^ 32 уникальных значения - около 4 миллиардов. Даже если вы использовали unsigned int (это не так), тип int нельзя использовать для хранения чисел, превышающих 4 миллиарда. Ваше число на несколько порядков больше этого, и, как таковое, когда вы пытаетесь поместить свой ввод в переменную int, что-то происходит, но я могу сказать вам, что не происходит: ему не присваивается значение 1231231231231236 .

Answer 2

Данное число слишком велико для целого числа в C. Вероятно, оно приняло только его часть.Попробуйте напечатать значение n.

Answer 3

Трудно понять без подробностей, но если ваши int 32-битные, то переданное вами значение находится за пределами допустимого диапазона, который, без сомнения, будет представлен как нечто иное, чем значение, которое вы указалипрошло.Вы можете рассмотреть возможность использования unsigned int вместо.