Решето Эратосфена C++ Бесконечный цикл

Итак, я работал над проблемой в книге Бьерна Страуструпа Programming: Principles and Practices Using C++ для собственной выгоды, и эта проблема ставит меня в тупик уже пару дней.

Я должен реализовать классический алгоритм решета Эратосфена с помощью инструментов, изученных в главе 4 (это немного), и это то, что у меня есть до сих пор:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int p = 2;
    int n = 0;
    vector<int> nums{ 1, 1 };

    cout << "Enter an integer greater than 1:\n";
    cin >> n;

    for (int i = 2; i <= n; ++i)
        nums.push_back(0);

    while (p < sqrt(n))
    {
        for (int i = 2; (i*p) <= n; ++i)
        {
            nums[i*p] = 1;
        }

        for (int i = (p+1); i <= n; ++i)
        {
            if (nums[i] == 0)
            {
                p = i;
                break;
            }
        }
    }

    for (int i = 0; i <= n; ++i)
    {
        if (nums[i] == 0)
            cout << i << '\n';
    }

    return 0;
}

Этот код ТААААО близок к работе, но не сигара. Он печатает только простые числа после 5 включительно, он не печатает 2 или 3. Я знаю, что проблема связана с тем, что мой цикл маркировки помечает nums[2] и nums[3], поэтому я попытался добавить следующую строку кода, чтобы гарантировать, что 2 и 3 не отмечены, потому что они использовались в качестве начальных значений p:

nums[p] = 0;

Я поместил эту строку между двумя циклами for, вложенными в цикл while. Я понятия не имею, как, но это каким-то образом вызывает бесконечный цикл, который я пытался исправить часами. Я действительно в своем уме здесь.

ПРИМЕЧАНИЕ. Я тестировал это с n = 23.


person Anthony Rossello    schedule 15.10.2015    source источник
comment
поскольку цикл вашего маркера for начинается с 0, каждый раз, когда вы находите простое число, он также помечает 0 и p как не простое число. В вашем случае, начиная с 5>sqrt(23), цикл маркера не запускается для любого простого числа больше 3, поэтому вы возвращаете эти простые числа, но 2 и 3 - несчастливые :-)   -  person triple_r    schedule 15.10.2015
comment
Спасибо за комментарий. К сожалению, запуск цикла маркера с i = 2 также приводит к бесконечному циклу!   -  person Anthony Rossello    schedule 15.10.2015
comment
Если вы вносите важное исправление, например, i=0 меняется на i=2, а код по-прежнему не работает, отредактируйте исходное сообщение, чтобы показать версию, с которой вам нужна помощь. Не говорите нам, что вы исправили эту ошибку, оставляя нас гадать, правильно ли вы ее исправили.   -  person JSF    schedule 16.10.2015
comment
Я думаю, что nums{ 1 1 } означает длину 1 и значение 1. Но я подозреваю, что вы хотели, чтобы элементы 0 и 1 были равны 1.   -  person JSF    schedule 16.10.2015
comment
Это потому, что в цикле после цикла маркера вы начинаете искать первое простое число из 0, которое всегда будет 2. Таким образом, вы всегда отмечаете числа, кратные 2, и никогда не получаете p, превышающее 2. Во втором цикле for начните поиск следующего простого числа с p + 1.   -  person triple_r    schedule 16.10.2015
comment
@triple_rr Вы должны написать свои ответы как ответ.   -  person Alan Stokes    schedule 16.10.2015
comment
@AlanStokes спасибо за предложение, я так и сделаю :-)   -  person triple_r    schedule 16.10.2015
comment
@triple_rr Это решило проблему! Затем я проверил значение 46 и обнаружил, что оно печатает 46 в конце списка простых чисел, хотя это явно не простое число. Чтобы решить эту проблему, я изменил условие в цикле маркеров с '‹' на '‹=', и это устранило ошибку.   -  person Anthony Rossello    schedule 16.10.2015


Ответы (1)


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

Поскольку следующий цикл всегда начинается с 0 и ищет следующее простое число, он всегда будет находить 2, и это вызовет бесконечный цикл.

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

    for(int i = p + 1; i <= n; ++i)
person triple_r    schedule 15.10.2015