Итак, я работал над проблемой в книге Бьерна Страуструпа 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.
for
начинается с0
, каждый раз, когда вы находите простое число, он также помечает0
иp
как не простое число. В вашем случае, начиная с5>sqrt(23)
, цикл маркера не запускается для любого простого числа больше3
, поэтому вы возвращаете эти простые числа, но2
и3
- несчастливые :-) - person triple_r   schedule 15.10.2015i=0
меняется наi=2
, а код по-прежнему не работает, отредактируйте исходное сообщение, чтобы показать версию, с которой вам нужна помощь. Не говорите нам, что вы исправили эту ошибку, оставляя нас гадать, правильно ли вы ее исправили. - person JSF   schedule 16.10.2015nums{ 1 1 }
означает длину 1 и значение 1. Но я подозреваю, что вы хотели, чтобы элементы 0 и 1 были равны 1. - person JSF   schedule 16.10.20150
, которое всегда будет2
. Таким образом, вы всегда отмечаете числа, кратные2
, и никогда не получаетеp
, превышающее2
. Во втором циклеfor
начните поиск следующего простого числа сp + 1
. - person triple_r   schedule 16.10.2015