Это одна из проблем, с которой сталкиваются все начинающие программисты: как проверить, является ли число простым, и обычно идея заключается в следующем:

• Сделайте счетчик, начиная с 2, дойдите до самого числа и проверьте с помощью функции по модулю.
  (Вопрос: действительно ли вы должны заходить так далеко? Представьте, что вы проверяете 37, действительно ли ваш счетчик должен дойти до 36?)
• Сделайте счетчик, начиная с 2, дойдите до половины самого числа и проверьте с помощью функции по модулю.
  (Опять тот же вопрос, нужно ли заходить так далеко? Представьте, что вы проверяете 391, когда у вас есть 17 и 23, у вас уже есть все из них. Так что не нужно идти выше... (не половины, а . ..номера))
• О, вы правы: создайте счетчик, начиная с 2, дойдите до квадратного корня из самого числа и проверьте, используя функцию по модулю.

Более полезно, если вы хотите стать программистом на языке C... Что произойдет, если я введу «лягушку» в качестве минимального значения. Теперь вы входите в мир обнаружения и восстановления ошибок.

Есть несколько способов улучшить сам алгоритм обнаружения простых чисел. Ранее на него уже давался подробный ответ, например. здесь, поэтому не буду углубляться в это.

Далее возникает вопрос о том, как проверить ввод. scanf() возвращает количество успешно преобразованных значений, поэтому его необходимо проверить, чтобы убедиться, что пользователь ввел допустимое целое число. Также следует проверить, находятся ли значения в допустимом диапазоне. Функция check() предполагает, что аргумент является положительным целым числом, поэтому либо ее необходимо сделать устойчивой к неположительному целому числу, либо гарантировать, что она будет вызываться только с положительным целым числом.

В частности, проверку можно изменить на:

    if (number <= 1)
    {
        return 0;
    }

Однако, возможно, лучше проинформировать пользователя, если введенные данные кажутся неправильными. В целом функцию main() можно записать следующим образом:

int main()
{
    int i,min,max;
    printf("Enter start of range: ");
    if (scanf("%d",&min) != 1)
    {
       printf("Input must be an integer\n");
       return 0;
    }
    if (min < 1)
    {
       printf("Input must be a positive integer\n");
       return 0;
    }
    printf("Enter end of range: ");
    if (scanf("%d",&max) != 1)
    {
       printf("Input must be an integer\n");
       return 0;
    }
    if (max < min)
    {
       printf("Range is empty\n");
       return 0;
    }
    for (i = min;i <= max;i++)
    {
        if (check(i) == 1)
        {
            printf("%d\n",i);
        }
    }
}

Примечание. В цикле for я изменил конечное условие на i <= max, поскольку пользователь, скорее всего, ожидает, что конец диапазона будет включен в проверяемые значения.

Как показывает этот пример, часто легко создать программу, которая работает, когда все идет хорошо. Создать программу, достаточно устойчивую ко всем исключениям, значительно сложнее.

Ваша программа работает так, как и ожидалось, при правильном вводе, и это хорошее начало. Вот способы улучшить код, особенно функцию check по запросу:

• используйте правильный прототип main без аргументов: int main(void).
• проверьте правильность ввода: scanf() возвращает 1, было ли введено целое число, в противном случае вам придется обработать ошибку явно.
• используйте более поясняющее имя для функции check, например isprime.
• в C идиоматично, что логические функции возвращают 0 в случае ложности и ненулевое значение в случае истины. Просто тестирование if (isprime(i)) более читабельно.
• проверьте наличие дополнительных значений для отклонения: if (n < 2) вместо if (n == 1). Если вы не можете предположить, что аргумент n равен как минимум 2, вам нужно использовать такой тест, чтобы отклонить более низкие значения. Используя другой цикл, вы могли бы попытаться избежать этого теста, но это того не стоит: этот тест прост и удобен для чтения и почти ничего не будет стоить, если большинство значений верны.
• проверка остатков деления должна прекратиться, как только частное станет меньше делителя.
• явное тестирование 2 перед циклом и проверка только нечетных делителей в цикле еще больше улучшит производительность.
• для вычисления простых чисел в диапазоне пробное деление менее эффективно, чем древнее Решето Эратосфена.

Вот модифицированная версия:

#include <stdio.h>

int isprime(int number)
{
if (number < 2) {
return 0;
}
if (number % 2 == 0) {
return number == 2;
}
for (int divisor = 3;; divisor += 2) {
// optimizing compilers will likely compute both the
// quotient and remainder with a single instruction
int quotient = number / divisor;
int remainder = number % divisor;
if (quotient < divisor)
return 1;
if (remainder == 0)
return 0;
}
}

int main(void)
{
int i, min, max;

printf("Enter start of range: ");
if (scanf("%d", &min) != 1) {
printf("invalid input\n");
return 1;
}
printf("Enter end of range: ");
if (scanf("%d", &max) != 1) {
printf("invalid input\n");
return 1;
}
for (int i = min; i < max; i++) {
if (isprime(i)) {
printf("%d\n", i);
}
}
return 0;
}

Помимо проверки того, является ли каждое число в диапазоне простым, есть и другие подходы:

Решето Эратосфена

Это алгоритм генерации всех простых чисел от 1 до N.

Его временная сложность O(max log log max) делает его намного быстрее. Однако для больших чисел у него есть недостатки, такие как высокие требования к пространству и перегрузка кэша. Существуют варианты алгоритма, которые решают эти проблемы, например «Сегментированное сито» и «Инкрементное сито».

Предварительно вычисленный массив

Для 32-битного целого числа существует 105'097'565 положительных простых чисел. Вы можете написать программу для их создания или найти в Интернете архивные файлы с ними и использовать их. Затем вы помещаете их в свою программу (например, в файл, который читает ваша программа).

Вы можете сохранить их как упорядоченный массив целых чисел, а затем найти позицию первого простого числа в вашем диапазоне в O(log n) с помощью двоичного поиска (на самом деле это O (1), потому что n — константа 105'097'565). Затем вы просто идете и печатаете массив, пока не получите число, превышающее ваш max.

Соображения сложности

Если вы только начали использовать C, на данном этапе эти параметры могут оказаться для вас слишком сложными.

Однако знать о них полезно, даже если вы не понимаете и половины того, что читаете. Затем, после того, как вы узнаете и попрактикуетесь больше, вы сможете вернуться к ним и попытаться реализовать их. И гордитесь тем, как далеко вы продвинулись 😁

[немного опоздал на главную вечеринку]

Как мне сделать это лучше?

Исправить прайм-чек

check(0) сообщает правду. check(any_negative) сообщает правду. Оба должны сообщить ложь.

Слишком медленно

check(n) повторяется до n раз. Простое изменение будет повторяться не более sqrt(n) раз. Для крупных n это в 10 000 раз быстрее.

Выполняйте итерацию, пока делитель меньше или равен частному.

int prime_check(int number) {
  if (number % 2 == 0) {
    return number == 2;
  }
  // Do not use divisor*divisor <= number as that overflows for a large prime.
  // Good compilers emit efficient code for number / divisor and
  // nearby number % divisor, doing both for the time cost of one.
  for (int divisor = 3; divisor <= number / divisor; divisor += 2) {
    if (number % divisor == 0) {
      return 0;
    }
  }
  return number > 1;
}

Сомнительный макс

Я ожидаю, что max будет частью тестируемого диапазона.

  printf("Enter end of range: ");
  scanf("%d",&max);
  // for (i = min; i < max; i++)
  for (i = min; i <= max; i++)

Но это проблема, когда max == INT_MAX.

Я поделюсь с вами еще одним подходом к достижению вашей цели.

Первое примечание: чтобы избежать проверки «номер 1» при каждом вызове функции проверки, переместите элемент управления if за пределы этой функции и за пределы себя для цикла. Таким образом, вы сможете выполнить эту проверку один раз.

Второе примечание: используйте рекурсивную функцию для создания итеративной проверки каждого числа, которое вы хотите проанализировать.

Функция проверки станет:

int check(int counter, int number)
{
    
    if (number%counter){
        //mod result is not zero
        //increase counter
        counter++;

        //if counter is equal to number
        //it means that number is prime - return 1 to caller!
        //otherwise call check function again with new counter value
        if (counter==number)
            return 1;
        else
            if (check(counter, number))
                //check returns 1 - number is prime! return 1 to caller
                return 1;  
            else
                //check returns 0 - number is not prime! return 0 to caller
                return 0;
    }else{
        //number is not prime
        //return 0 to caller
        return 0;
    }

}

используя рекурсивный вызов, вы можете выполнять итеративные проверки без использования цикла, с точки зрения квантового времени вы можете сэкономить ресурсы и повысить эффективность.

Вот мой полный код с комментариями:

#include <stdio.h>

//declare functions
int check(int counter, int number);

int main()
{
    int i,min,max;
    printf("Enter start of range: ");
    scanf("%d",&min);
    printf("Enter end of range: ");
    scanf("%d",&max);
    
    // if first number is 1, i'll skip it
    if (min == 1){
        min++;
    }

    if (min == 2){
        //2 is prime, print it and increment min
        printf("%d\n",min++);
       
    }

    for (i = min;i <= max;i++)
    {
   
        
        //call recursive function for checking prime
        if (check(2,i))
            printf("%d\n",i);
        

    }
    return 0;
}


/*check function is recursive.
*  it acceptes counter and number values
*  perform prime check:
*    - it's prime number - recursive function stack will be close and return 1
*    - it's not prime number - counter will be increased and check function will be called again from itself
*/  
int check(int counter, int number)
{

    if (number%counter){
        //mod result is not zero
        //increase counter
        counter++;

        //if counter is equal to number
        //it means that number is prime - return 1 to caller!
        //otherwise call check function again with new counter value
        if (counter==number)
            return 1;
        else
            if (check(counter, number))
                //check returns 1 - number is prime! return 1 to caller
                return 1;  
            else
                //check returns 0 - number is not prime! return 0 to caller
                return 0;
    }else{
        //number is not prime
        //return 0 to caller
        return 0;
    }

}

Плюсы: очищенная компоновка кода, меньше затрат времени.

Минусы: немного сложнее, меньше используется стековая память.

Последние соображения: для дополнительных улучшений вам следует реализовать элементы управления входными данными (минимальные и максимальные значения), чтобы избежать непредвиденного поведения.

Обновлено: я изменил указатели удаления кода и перемещение использования памяти стека в минусах.

Несколько лет назад я взял это из книги, возможно, «Алгоритмы на C», в которой sqrt() и floor() используются для определения момента разрыва цикла, с несколькими моими небольшими дополнениями:

/* return 1 if n is a prime number  */
int is_prime(unsigned int n) {
    unsigned int spia,f;
    if ( !n ) return 0;
    if ( n <= 3 ) return 1;
    if ( (n % 2) && (n % 3) ) {
      spia = (unsigned int) floor(sqrt(n));
      for ( f=5 ; (n % f) && (n % (f+2)) && f <= spia ; f+=6 ) ;
      if ( f > spia ) return 1;
    } // endif
    return 0;
}

Основываясь на предыдущих ответах, я проверил эту версию с удаленным sqrt() и замененным на / (целочисленное деление), чтобы посмотреть, когда разорвать цикл:

int is_prime_w_div(unsigned int n) {
    unsigned int f;
    if ( !n ) return 0;
    if ( n <= 3 ) return 1;
    if ( (n % 2) && (n % 3) ) {
      for ( f=5 ; (n % f) && (n % (f+2)) ; f+=6 ) {
            if ( f > n/f ) break;
      } // endfor
      if ( f > n/f ) return 1;
    }
    return 0;
}

Я замерил обе версии по 10 миллионам целых чисел (от 0 до 10000000) как на Raspi400 под управлением Raspbian Linux, так и на Geekom Mini IT13 Core i9-13900H под управлением OpenSuse Leap15.6, и в обоих случаях версия sqrt() была самой быстрой:

/* testprime.c */
#include <stdio.h>
#include <math.h>

/* put is_prime and is_prime_w_div here */

int main(void) {
  unsigned int i,cnt;
  for ( cnt=0,i=0 ; i<10000000 ; i++) {
    if (is_prime(i)) cnt++;
    /* if (is_prime_w_div(i)) cnt++; */
  } /* endif */
  printf("found %u primes\n",cnt);
  return 0;
}

/*
 * gcc testprime.c -lm
 * time ./a.out
 */ 

Так что за история? На современном оборудовании математические операции с плавающей запятой выполняются аппаратно, и sqrt() НЕ вызывается в цикле на каждой итерации. Или я что-то еще упускаю?