Каков наилучший способ генерации простых чисел?

Question

Я занимаюсь упражнениями программирования на языке C Кочаном; только на начальном этапе, глава 5.

Вот задача:

Программа 5,10 имеет несколько неэффективности. Одна неэффективность получается из проверки четных чисел. Поскольку очевидно, что любое четное число больше 2 не может быть простым, программа может просто пропустить все четные числа как возможные простые числа и как возможные делители. Внутренний цикл также неэффективен, потому что значение p всегда делится на все значения d от 2 до. Эту неэффективность можно было бы избежать, добавив тест для значения is_prime в условиях цикла for. Таким образом, цикл for может быть настроен для продолжения до тех пор, пока не будет найден ни один делитель, а значение d меньше, чем p. Измените Программу 5.10, чтобы включить эти два изменения.

Вот программа 5,10

// generate a table of prime numbers 
    #include <stdio.h> 

    int main (void) 
    { 
     int p, d; 
     _Bool is_prime; 

     for (p = 2; p <= 50; ++p) 
     { 
      is_prime = 1; 

      for (d = 2; d < p; ++d) 
       if (p % d == 0) 
        is_prime = 0; 

       if (is_prime)   // or if (is_prime != 0); same 
        printf ("%i ", p); 
     } 

     printf ("\n"); 
     return 0; 
    } 

Вот два варианта я пытаюсь писать, но и распечатывают пустое пространство; номера не производятся. Первый может представлять собой совершенно неправильный подход, , но я не понимаю, почему второй не сработает.

Вариант 1:

// generate a table of prime numbers 
#include <stdio.h> 
#include <stdbool.h> 

int main (void) 
{ 
    int p, d; 
    bool is_prime; 

    /* start from p=2, do until p is less than 50, 

    and skip all even numbers */ 

    for (p = 2; (p < 50) && (p % 2 != 0); ++p) 

    { 
     is_prime =1; 

     /* the inner for loop says: start from d = 2; do until 
     d is less than p, and also test if p is prime or not by 
     dividing p by d */ 

     for (d = 2; d < p (p % d != 0 ? is_prime : !is_prime); ++d) 

      printf ("%i ", p); 
    } 

    printf ("\n"); 
    return 0; 
} 

Вариант 2:

// generate a table of prime numbers 
#include <stdio.h> 
#include <stdbool.h> 

int main (void) 
{ 
    int p, d; 
    bool is_prime; 

    /* start from p=2, do until p is less than 50, 

    and skip all even numbers */ 

    for (p = 2; (p < 50) && (p % 2 != 0); ++p) 

    { 
     is_prime =1; 

     /* the inner for loop says: start from d = 2; do until 
     d is less than p, and also test if p is prime or not by 
     dividing p by d */ 

     for (d = 2; (d < p) && (p % d != 0); ++d) 
      /* this inner loop was supposed to print the number if 
      it is not divided by d */ 

      printf ("%i ", p); 
    } 

    printf ("\n"); 
    return 0; 
} 

Я был бы признателен за вашу помощь! Я новичок в программировании.

Спасибо!

Answer 1

Хммм ....

#include <stdio.h> 
#include <stdbool.h> 
int main(void) { 
    unsigned int d = 0; 
    unsigned int p = 0; 
    bool is_prime = false; 
    // We know 2 is prime 
    printf("%u ", 2); 
    for (p = 3; p < 50; p += 2) { 
    // Skipped even numbers 
    is_prime = true; 
    // Since 2 is prime and we got rid of even numbers 
    // We can just check odd divisors by starting with 3 and incrementing by 2 
    for (d = 3; d * d < p && is_prime == true; d += 2) { 
     // If we have a divisor, it's not prime 
     if (p % d == 0) { 
     is_prime = false; 
     } 
    } 
    // This was outside the loop in the original program 
    if (is_prime) { 
     printf("%u ", p); 
    } 
    } 
    return 0; 
} 

Во-первых, мы знаем, 2 наше единственное даже простое, так чтобы упростить, мы идем вперед и распечатать его и начать с 3. Так как ни одна другая четное число не является простым , мы увеличиваем на 2 каждый цикл (помните - цикл for останавливается, когда условие ложно, поэтому мы не можем сказать p % 2 != 0 как условие цикла). Мы устанавливаем is_prime в true, а затем проверяем все нечетные делители. Если найден делитель, число не является простым и мы прекращаем тестирование; в противном случае число является простым. Опять же, поскольку 2 - единственное четное простое, мы можем пропустить четные делители. Наконец, если мы пропустим квадратный корень из числа, то число, как гарантируется, будет простым.

Answer 2

Поскольку вы все еще учатся, я хотел бы рассмотреть разрушение некоторых частей, например создание isPrime функции, например:

int isPrime(int num) { 
    int i; 
    for (i = 2; i < num; i++) { 
     if (num % i == 0 && i != num) 
      return 0; 
    } 
    return 1; 
} 

Затем, вы можете использовать его в свои подходы, например:

#include <stdio.h> 

int main() 
{ 
    int p, d; 

    /* Avoid (p == 2) comparison each iteration */ 
    printf ("2 "); 

    /* Go from 3 to 49 and print prime numbers without checking even numbers */ 
    for (p = 3; p < 50; ++p) { 
     if (p % 2 != 0){ 
      if (isPrime(p)) 
       printf ("%i ", p); 
     } 
    } 

    return 0; 
} 

Конечно, существует много разных способов, и вы должны рассмотреть возможность использования библиотеки времени (возможно, time.h) для оценки производительности.

Answer 3

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

for (p = 2; (p < 50) && (p % 2 != 0); ++p) 

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

(2 < 50) && (2 % 2 != 0) == true && (0 != 0) == true && false == false Таким образом, потому что ваш охранник петли изначально ложно, то цикл никогда не будет работать.

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