Calculating primes: Could this be any faster? I've ported a prime-number calculation program from primes.pyx to C++ for benchmark purpose.
Since I wrote it in C++, I thought that my program would be faster than the original. However, mine took 25.8 ms at the fastest, while the original took only 1.45 ms on the same machine. I tested 10 times each, but got similar results (25.8~51.7ms vs 1.45~1.47ms). But, why?
Here's my code:
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;chrono&gt;
using namespace std;

vector&lt;int&gt; primes(size_t nb_primes)
{
    int n;
    vector&lt;int&gt; p;
    p.reserve(nb_primes);

    n = 2;
    while (p.size() &lt; nb_primes)
    {
        bool other = true;
        for (size_t i = 0; i &lt; p.size(); i++)
        {
            if (n % p[i] == 0)
            {
                other = false;
                break;
            }
        }
        if (other)
            p.push_back(n);
        n += 1;
    }
    return p;
}

int main()
{
    auto start = std::chrono::high_resolution_clock::now();

    vector&lt;int&gt; p = primes(1000);
    //for (auto i : p)
    //    cout &lt;&lt; i &lt;&lt; ' ';

    auto finish = std::chrono::high_resolution_clock::now();

    std::chrono::duration&lt;double&gt; elapsed = finish - start;
    std::cout &lt;&lt; &quot;Elapsed Time: &quot; &lt;&lt; elapsed.count() &lt;&lt; &quot; s\n&quot;;
}

These algorithms are exactly the same, I believe.
Please don't limit the check up to sqrt(n), to achieve a sieve of Eratosthenes.
I need to compare with the original.
One thing I'm worried is the for ... else statement in the original.
I borrowed the idea to use the other flag from Username: haccks.
If you can apply another for ... else method, please go ahead.
My Windows 10 machine (i5) spec:
Clock Frequency: 1.60GHz 1.80GHz
Memory: 8.00GB
I wrote the original version on Anaconda Prompt/Python 3.8.
I write the C++ version on Visual Studio 2019.
If you need more information, please ask me.
Thank you in advance.
There are some optimizations that can make your code better, even with compiler optimizations turned on:
Pre-allocate the vector and treat it like an array.
Use a variable to keep track of the length.
Putting these together, I found about a 10% increase in speed:
vector&lt;int&gt; primes(size_t nb_primes)
{
    vector&lt;int&gt; p(nb_primes,2);
    int n = 2;
    size_t len_p = 0;
    while (len_p &lt; nb_primes)
    {
        bool other = true;
        for (size_t i = 0; i &lt; len_p; i++)
        {
            if (n % p[i] == 0)
            {
                other = false;
                break;
            }
        }
        if (other)
            p[len_p++] = n;
        n += 1;
    }
    return p;
}