Как мне исправить мою программу Prime Generating, начиная от составных чисел - PullRequest
Новая
       7

Как мне исправить мою программу Prime Generating, начиная от составных чисел

0 голосов
/ 10 января 2020

Я пытаюсь написать программу на C ++, которая будет вычислять простые числа и сохранять их в массиве. Считайте, что это мой третий код.

Проблема, с которой я столкнулся, заключается в том, что, в то время как я получаю простые числа, я также получаю составные числа, в частности, кратные 5 и 7 (по крайней мере, до предела 30). Я знаю, что код, вероятно, будет ужасным, но это было то, что я мог придумать, учитывая мой ограниченный опыт в кодировании и простых числах.

Это то, что я написал: 

#include <iostream>
int j;
int i = 3;
int prime[30];

int main()
{
    for (i; i < 30; i+=2)
    {
        for (j =i; j>i*i; j--)
        {
            if ((i % j) == 0)
            {
                continue;
            }
        }
        prime[i] = i;
        std::cout << prime[i] << std::endl;
    }
}

вывод: 3 5 7 9 11 13 15 17 19 21 23 25 27 29

Ответы [ 2 ]

1 голос
/ 10 января 2020

Ваш внутренний l oop нуждается только в проверке делимости с простыми числами, с которыми вы встречались до сих пор. (например, нет смысла проверять делимость с 9, если вы уже проверяли делимость с 3) 

int main()
{
    int j;
    int i = 3;
    int primes[30];
    int primecount = 0;

    primes[primecount++] = 2;  // hardcode 2, it's the only even number

    for (i = 3; i < 30; i += 2)
    {
        bool isPrime = true;

        for (j = 0; j < primecount; j++)
        {
            if ((i % primes[j]) == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes[primecount++] = i;
        }
    }

    for (int k = 0; k < primecount; k++)
    {
        std::cout << primes[k] << " ";
    }
    std::cout << std::endl;
}
0 голосов
/ 11 января 2020

Как CoderCharmander указывает в комментариях , что continue разрывается только от внутреннего l oop, но вы намеревались продолжить с наружный л oop. Наименьшее исправление заключается в использовании страшного goto, вполне уместного здесь.

Также неверна внутренняя спецификация for l oop: 

#include <iostream>

int prime[30];

int main()
{
    int i, j;
    std::cout << 2 << " ";     // the first prime is 2
    for (i=3; i < 30; i+=2)
    {
        for // all wrong: (j =i; j>i*i; j--)
            (j = 2; j*j <= i; ++j)    // or even, (j = 3; j*j <= i; j += 2)
        {
            if ((i % j) == 0)
            {
                prime[i] = 0;  // initialize the non-primes as well!
                goto L1;       // continue the outer loop
            }
        }
        // the inner loop finished normally
        prime[i] = i;  
        std::cout << i << " ";

        L1: ;
    }
}

Это также без необходимости проверяет числа на все числа выше 2, меньшие, чем пороговое значение (или шансы, как в прокомментированном предложении), но нам действительно нужно проверять только простые числа.

При внесении этой поправки важно быть осторожным, чтобы не вводить гораздо большую неэффективность, чем та, которую мы пытались исправить ( квадратик c потеря во временной сложности по сравнению с намеченным log коэффициент усиления), так как нет смысла проверять делимость, например, на 23 на 5,7,11,13 и 19.

А на самом деле проверяемую делимость можно вообще избежать если кто-то так решит, но это совсем другое дело.

...