Цикл не быстрее, несмотря на то, что проходит через половину столько итераций? - PullRequest
Новая
       13

Цикл не быстрее, несмотря на то, что проходит через половину столько итераций?

0 голосов
/ 01 сентября 2018

Я написал программу, которая ищет простые числа: 

#include <iostream>
#include <fstream>
#include <chrono>

typedef std::chrono::high_resolution_clock Clock;
using namespace std;

int main() {
    int p;
    int x = 1;
    int b;
    int a[1000000];
    bool n = false;
    a[0] = 2;
    a[1] = 3;

    auto t1 = Clock::now();

    ofstream outfile;
    outfile.open("p.txt");

    for (p = 3; p < 7500000; p = p + 2)
    {
        for (b = 0; b <= x && n == 0; b++)
        {
            if (p % a[b / 2] == 0)
            {
                n = true;
            }
        }
        if (n == false)
        {
            cout << p << endl;
            outfile << p << endl;
            x++;
            a[x] = p;
        }
        else
        {
            n = false;
        }
    }

    auto t2 = Clock::now();
    std::cout
        << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count()
        << " nanoseconds" << std::endl;
    outfile.close();
}

Первоначально для приращения цикла у меня было p++, но я изменил это на p=p+2, потому что все простые числа в основном нечетные и четные числа проверять не нужно. Проблема в том, что, когда я тестировал это, не было никакой разницы в скорости между старым и новым кодом. Так что же является узким местом в процессе, если проверка всех чисел ничем не отличается от проверки половины? И есть ли лучший способ приблизиться к этому?

Ответы [ 2 ]

0 голосов
/ 01 сентября 2018

Вот эта строка: 

for(b=0; b<=x && n==0; b++)

После выполнения n=true; цикл b завершается из-за условия && n==0. Это происходит с самым первым тестом: каждое четное число делится на два, что составляет a[0]. Таким образом, для четных чисел (которые вы включаете, если используете p++ вместо p=p+2) внутренний цикл очень быстрый, намного быстрее, чем для обычного нечетного числа. Это объясняет, почему включение их так мало меняет.

0 голосов
/ 01 сентября 2018

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

Если вы не видите, что ваш внутренний цикл выполняет все дважды, учтите, что a[b/2] - это то же самое, когда b равно 1, как и тогда, когда b равно 0.

...