связанный список — C ++ Сито Эратосфена находит 3 слишком много простых чисел
У меня есть программирование, чтобы написать программу на C ++, которая находит все простые числа меньше N (пользовательский ввод). Половина задания касается сита Эратосфена. Мой код работает (читай: назначение завершено), но до того, как я отредактировал вывод, он безоговорочно распечатывался п-3, н-2, а также н-1 как простые числа, даже если они не были простыми. Я не уверен, почему это происходит. Буду признателен за отзывы и идеи о том, почему программа действует так, как она есть. Вот неизмененный код:
Обратите внимание, что я я используя класс ListNode и класс LinkedList, оба из которых являются полностью функциональными. РЕДАКТИРОВАТЬ: частично основной добавлен; обратите внимание на второй пункт в за петля 3 Размер. Если это осталось в размер, программа выводит 3 дополнительных не простых числа.
int main()
{
for(int i = 0; i<my_list.size()-3; i++)
{
if(marked[i]==true)
cout<<my_list[i]<<"\n";
}
}
void eratosthenes(int item)
{
bool run=true;
int p=2, count=0;
for(int i=2; i<=item; i++)
{
my_list.append(i); // Entire list is filled with integers from 2 to n
marked.append(true); // Entire list is filled with true entries
}
while(run==true&&(2*p)<item)
{
count = 0;
int i = (2*p);
do {
marked[i-2]=false; // marked values are false and not prime
i+=p;
} while(i<item-2);
for(int i=0; i<item-2; i++) // i starts at 0 and increments by 1
{ // each time through the loop
if(my_list[i]>p)
{
if(marked[i]==true) // If a value stored in a node is true
{ // (prime), it becomes the new p.
p=my_list[i]; // The loop is then broken.
break;
}
}
}
for(int j=1; j<item-2; j++)
{
if(marked[j]==false)
{
count=1;
}
}
if(count==0)
run=false;
}
Решение
Из вашего кода:
do{
marked[i-2]=false;//marked values are false and not prime
i+=p;
}while(i<item-2);
Этот цикл отвечает за прохождение всех номеров i которые являются целыми числами, кратными простому числу p и маркировка их не проста, как я понимаю. Почему вы останавливаетесь на условии i < item - 2? Это было бы хорошо, если i были вашим индексом для my_list а также marked списки, но в этом случае это не так; это фактическое число, которое вы отмечаете, а не простое число. Я подозреваю, что именно поэтому вы получаете числа, близкие к вашему пределу (item), которые помечены как простые — ваш цикл здесь выходит раньше i когда-нибудь доберусь до этих цифр!
Кстати, вместо этого вы можете сделать это как цикл for, который будет легче читать. Цикл for имеет значение «проходить через каждый элемент в наборе» (будь то последовательные целые числа, или каждое n-е целое число, или элементы в массиве / списке / deque и т. Д.), Поэтому программист, читающий ваш код, сразу же узнает об этом и не нужно выяснять это из вашего цикла while.
// mark every multiple of the current prime as not prime
for(int i = 2*p; i < item - 2; i += p)
{
marked[i-2] = false;
}
(Это так же, как ваш исходный код, исправления не применяются).
Некоторые общие комментарии по улучшению вашего алгоритма / кода:
Попробуйте использовать более описательные имена переменных. Ваше использование i два раза означать разные вещи сбивает с толку, и, как правило, отдельные буквы мало что значат для того, что представляет переменная (хотя иногда их достаточно, например, цикл for, где i это индекс списка / массива).
Кроме того, вы просматриваете свой список намного больше, чем нужно. Минимум, который требуется алгоритму решета Eratosthenes, — это два вложенных цикла for (не включая инициализацию списка / массива для всех true).
Одним из примеров того, где вы выполняете больше работы, чем необходимо, является цикл, начиная с индекса 0, чтобы найти следующий p использовать — вместо того, чтобы просто помнить, где ваш текущий p и начиная с этого. Вам даже не нужно проверять my_list[i] > p в этом случае, так как вы знаете, что вам не по силам начать. Кроме того, ваш последний цикл может break; рано и избегайте продолжения после того, как он найдет не простое число (и я не уверен, какой в этом смысл).
Второй ответ Николая Митева — более эффективная и более читаемая реализация решета (но заменить ), хотя он на самом деле не дал много комментариев или объяснений по этому поводу. Первый цикл — «пройти через все числа до upperBound»; внутри него, «если текущее число простое, пройдите все кратные этому простому и отметьте их не простыми». После выполнения этого внутреннего цикла внешний цикл продолжается, проходя через следующие числа — не нужно начинать с начала или даже вводить другой цикл for, чтобы найти следующее простое число.sqrt(upperBound) с upperBound/2 чтобы он работал правильно; причина для upperBound/2 должно быть довольно ясно из того, как работает сито
РЕДАКТИРОВАТЬ: sqrt(upperBound) верно. Я не думал об этом достаточно тщательно.
Другие решения
Полный метод
void Eratosthenes(int upperBound)
{
bool Prime[upperBound];
for(int i = 0;i<upperBound;i++)
Prime[i]=true;
for (int i = 2; i <= sqrt(upperBound); i++)
{
if (Prime[i])
{
for (int j = i * 2; j < upperBound; j += i)
Prime[j] = false;
}
}
for(int i=2;i<upperBound;i++)
{
if(Prime[i]==true)
cout<<i<<" ";
}
}
Почему бы вам не работать с массивом логических значений для простоты, начиная с индекса 2, и когда вы напечатаете результат, вы напечатаете индексы со значением true