小编Apo*_*aju的帖子

问题陈述是要在20秒钟内找到20亿以下的质数。我遵循以下方法。

1. 将数字n除以数字k的列表（k <sqrt（n）） -花费了20秒

2. 将数字n除以sqrt（n）以下的质数列表。在这种情况下，我将质数存储在std :: list中-花费了超过180秒的时间

有人可以帮助我理解为什么即使我们将除数都减少了50％（大约），第二种方法仍要花很长时间？还是我选择了错误的数据结构？

方法1：

#include <iostream>
#include<list>
#include <ctime>
using namespace std;

list<long long> primeno;
void ListPrimeNumber();

int main()
{
    clock_t time_req = clock();
    ListPrimeNumber();
    time_req = clock() - time_req;
    cout << "time taken " << static_cast<float>(time_req) / CLOCKS_PER_SEC << " seconds" << endl;
    return 0;
}

void check_prime(int i);

void ListPrimeNumber()
{
    primeno.push_back(2);
    primeno.push_back(3);
    primeno.push_back(5);
    for (long long i = 6; i <= 20000000; i++)
    {
        check_prime(i);
    }

}

void check_prime(int …