Простые числа с использованием сита эрастосфена в C
Я написал следующую программу для отображения всех простых чисел до 150. Она не выполняется вообще. что в этом плохого?
# include <stdio.h>
int main(void)
{
int p[150], i, j;
for (i = 2; i < 150; i++)
p[i] = 0;
i = 2;
while (i < 150){
if (p[i] == 0)
printf("%i ", i);
for (j = 1; i*j <= 150; j++)
p[i*j] = 1;
i++;
}
return 0;
}
3 ответа
Решение
i*j <= 150
неверно, должно быть i*j < 150
, поскольку p
массив имеет элементы из 0
в 149
, Из-за этого программа застревает в бесконечном цикле.
РЕДАКТИРОВАТЬ: Остальная часть этого ответа была неправильной, поэтому я удалил его.
- Вы получаете доступ
p[i*j]
, который находится за пределами допустимого диапазона [0-149]. Состояниеi*j <= 150
будет оценивать истину, когдаi*j
равен 150, что по одному. Так должно бытьi*j < 150
, - Поток stdout буферизуется. Вам нужно промыть в конце цикла. Попробуйте добавить
fflush(stdout)
, - Может иметь меньшее значение, но если вы заботитесь о результирующем массиве (например, хотите использовать его позже), значение
p[2]
ошибочно установлено в 1. Тем не менее, ваша программа будет по-прежнему печатать 2, но это потому, что ваш цикл печатает числа до изменения значенияp[i*j]
, В заключение, числа печатаются правильно, но значения в массиве не совсем корректны.
В качестве учебного упражнения попробуйте добавить несколько printf, чтобы узнать, что делает ваша программа.
Также имейте в виду, что, как говорит jweyrich, что printf без \n в нем не будет ничего выводить до (возможно) выхода из программы.