Блог

Итак, я новичок в C, и, хотя у меня есть опыт работы с python, я не могу разобраться в простой проблеме.

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

Итак, из руководств, которым я следовал, это код для поиска простых чисел от 3 до 100 с использованием массивов:

 #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main()
{
    int p;
    int i;

    int primes[50] = { 0 };
    int primeIndex = 2;

    bool isPrime;

    // hardcode prime numbers
    primes[0] = 2;
    primes[1] = 3;

    for (p = 5; p <= 100; p = p   2)
    {
        isPrime = true;

        for (i = 1; isPrime amp;amp; p / primes[i] >= primes[i];   i)
            if (p % primes[i] == 0)
                isPrime = false;

        if (isPrime == true)
        {
            primes[primeIndex] = p;
              primeIndex;
        }
    }

    for (i = 0;  i < primeIndex;    i)
         printf("%i  ", primes[i]);

    printf("n");
    return 0;
}
 

Первый for цикл в приведенном выше коде был понятен, но то, что произошло после второго, сбивает меня с толку.

Какова логика p / primes[i] >= primes[i] условия во втором цикле for?

Например, если я выполню цикл p = 5 и применю условие, это будет 5 / primes[1] >= primes[1] :

Поскольку мы знаем primes[1] = 3 , что это станет 5 / 3 >= 3 , что немедленно становится ложным.

Пожалуйста, объясните, что происходит после первого цикла for

Редактировать: я добавил код python, который я могу сделать сам. Почему невозможно сделать то же самое в C:

 lst = [2]
for i in range(3, 100):
     for j in range(2, i):
          if (i % j) == 0:
                break
     else:
          lst.append(i)

print(lst)

 

Внутренний for цикл проверяет все нечетные простые числа, найденные до сих пор, вплоть до включения sqrt(p) , без фактического вычисления sqrt(p) . Цикл останавливается, как только он находит простое число, которое равномерно делится p . Это может быть более читаемым как:

     isPrime = true;
    for (i = 1; p / primes[i] >= primes[i];   i) {
        if (p % primes[i] == 0) {
            isPrime = false;
            break;
        }
    }
 

В случае 5 , цикл to не запускается, потому 5 < 3*3 что , 5 является простым числом, то же самое для 7 : для определения его простоты тест не требуется.

Ваш код на python более элегантный благодаря else: предложению for оператора, которое выполняется только в том случае, если цикл завершается нормально. Тем не менее, алгоритм в версии python намного менее эффективен, поскольку вы проверяете все числа, включая четные и все делители до i . Для 100 разница едва заметна, но для гораздо больших диапазонов будет отображаться дополнительная сложность. Также обратите внимание, что это lst должно быть инициализировано, lst = [2] чтобы список простых чисел был правильным, и вы можете удалить if i > 1: то, что является избыточным.