Проблемы с решетом Эратосфена

Я взял "Принципы и практика программирования с использованием C++" и решал раннюю задачу, связанную с решетом Эратосфена, и у меня был неожиданный результат, но я не могу точно определить, в чем проблема. Вот мой код:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> prime;
    std::vector<int> nonPrime;
    int multiple = 0;


    for(int i = 2; i < 101; i++) //initialized to first prime number, i will 
       // be the variable that should contain prime numbers
        {
            for(int j = 0; j < nonPrime.size(); j++) //checks i against 
                                                      //   vector to see if 
                                                      //  marked as nonPrime
                {
                    if(i == nonPrime[j])
                        {
                            goto outer;//jumps to next iteration if number 
                                        // is on the list
                        }
                }

                prime.push_back(i); //adds value of i to Prime vector if it 
                                         //passes test

                for(int j = i; multiple < 101; j++) //This loop is where the 
                                                      // sieve bit comes in
                    {                           
                        multiple = i * j;           
                        nonPrime.push_back(multiple);
                    }
                outer:
                    ;
        }

        for(int i = 0; i < prime.size(); i++)
            {
                std::cout << prime[i] << std::endl;
            }


    return 0;
}

Вопрос только в настоящее время просит меня найти простые числа до 100, используя этот метод. Я также попытался использовать этот текущий метод «goto» для пропуска двойного цикла при определенных условиях, а также попытался использовать логический флаг с оператором if сразу после цикла проверки и просто использовал «продолжить;» заявление, и ни один из них не имел никакого эффекта.

(Честно говоря, я подумал, что, поскольку люди говорят, что goto был злом, возможно, он имел последствия, которых я не предвидел, поэтому я попытался отключить его), но проблема не требует от меня использования модульных функций, поэтому я предполагаю, что он хочет мне решить все это в main, поэтому моя проблема с использованием вложенных циклов в main. Да, и чтобы дополнительно указать мои проблемы с выводом, кажется, что он добавляет только кратные 2 к вектору nonPrime, но все остальное проверяется как прохождение теста (например, 9).

Может ли кто-нибудь помочь мне понять, где я ошибся?


person Aaron McAnally    schedule 12.03.2018    source источник
comment
Между прочим, отказ от колледжа не имеет большого значения для индустрии разработки программного обеспечения. Компании не заботятся о вашем формальном образовании. Академия в любом случае делает ужасную работу по обучению CS. Так что продолжайте в том же духе и читайте книги/онлайн-ссылки.   -  person Ron    schedule 12.03.2018
comment
@Ron Спасибо за поддержку, я очень ценю это. Книга довольно сухая, и кажется, что она не способствует обучению, но независимо от того, двинусь ли я дальше или нет, я все равно хотел бы хотя бы понять, что я сделал неправильно. Невозможно исправить свои ошибки, если вы не извлекаете из них уроки, я знаю это из своего личного опыта лучше, чем хотел бы признать. На другой заметке, получил рекомендацию книги? Всегда открыты для совета!   -  person Aaron McAnally    schedule 12.03.2018
comment
Пожалуйста. Не беспокойтесь об этом слишком сильно. Пропустите это двигаться дальше. Познакомьтесь с книгами Скотта Мейерса по эффективному C++, как только вы освоите язык. C++ — странный, но красивый зверь.   -  person Ron    schedule 12.03.2018
comment
Примечание: Решето Эратосфена обычно реализуется с большим массивом bool. vector::push-back станет дорогим и, вероятно, потребует столько же памяти.   -  person user4581301    schedule 12.03.2018
comment
@ user4581301 Понятно, я не знал. В книге не рассматриваются какие-либо методы, как это сделать, просто объясняются некоторые основные концепции и предлагается читателю сделать все возможное, спасибо за разъяснения. Я полагаю, оглядываясь назад, это то, что я должен был рассмотреть.   -  person Aaron McAnally    schedule 12.03.2018
comment
В Википедии есть отличная страница и рассказывается, как это работает. Демонстрационный GIF расскажет вам практически все, что вам нужно знать. и текст заполняет все остальное.   -  person user4581301    schedule 13.03.2018


Ответы (1)


Учитывая, что это не лучший способ реализовать решето Эратосфена, я укажу на некоторые изменения в вашем коде, чтобы он, по крайней мере, выдавал правильную последовательность.

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

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> prime;
    std::vector<int> nonPrime;
    int multiple = 0;


    for(int i = 2; i < 101; i++) 
    {
        // you can use a flag, but note that usually it could be more 
        // efficiently implemented with a vector of bools. Try it yourself
        bool is_prime = true;
        for(int j = 0; j < nonPrime.size(); j++)
        {
            if(i == nonPrime[j])
            {
                is_prime = false;
                break;
            }
        }

        if ( is_prime )
        {
            prime.push_back(i);
            // You tested 'multiple' before initializing it for every
            // new prime value
            for(multiple = i; multiple < 101; multiple += i)
            {                           
                nonPrime.push_back(multiple);
            }
        }
    }

    for(int i = 0; i < prime.size(); i++)
    {
        std::cout << prime[i] << std::endl;
    }

    return 0;
}
person Bob__    schedule 12.03.2018