c++ - ベクトルの反復処理が非常に遅いのはなぜですか?

Question

10,001 番目の素数を計算するProject Euler #7を実行しています。整数が素数であるかどうかを確認する簡単な関数を作成しました。

bool isPrime(int p)
{
    if (p % 2 == 0 || p <= 1)
    {
        return false;
    }
    for (int i=3; i<=(int)sqrt((double)p)+1; i+=2)
    {
        if (p % i == 0)
        {
            return false;
        }
    }
    return true;
}

次に、メイン プログラムで 2 から開始し、その後のすべての奇数を繰り返し、各素数を数えます。

int count(1);
int i(1);
while (count != 10001)
{
    i += 2;
    if (isPrime(i))
    {
        count++;
    }
}

std::cout << "Answer: " << i << std::endl;

次に、これまでに見つかったすべての素数を追跡し、次のように関数に入力することで、この関数を改善できると考えましたisPrime。

bool isPrime(int p, std::vector<int> primes)
{
    if (p <= 1) 
    {
        return false;
    }
    for (std::vector<int>::iterator it=primes.begin(); it!=primes.end(); it++)
    {
        if (p % *it == 0)
        {
            return false;
        }
        else if (*it > (int)sqrt((double)p)+1)
        {
            return true;
        }
    }
    return true;
}

メインプログラムは次のように変更されます。

int count(1);
int i(1);
std::vector<int> primes(1,2);
while (count != 10001)
{
    i += 2;
    if (isPrime(i, primes))
    {
        count++;
        primes.push_back(i);
    }
}

std::cout << "Answer: " << primes.back() << std::endl;

私のコードの最初のバージョンは 1 秒もかからずに答えを得ますが、2 番目のバージョンは 1 分以上かかります。これがなぜなのかわかりません。確かに、2番目のバージョンはisPrime、より小さな範囲の数値を反復しているため、より高速である必要がありますか? 誰かがアドバイスを提供できる場合は、ありがとう。