C++ Optimizing this Algorithm

Question

After watching some Terence Tao videos, I wanted to try implementing algorithms into c++ code to find all the prime numbers up to a number n. In my first version, where I simply had every integer from 2 to n tested to see if they were divisible by anything from 2 to sqrt(n), I got the program to find the primes between 1-10,000,000 in ~52 seconds.

Attempting to optimize the program, and implementing what I now know to be the Sieve of Eratosthenes, I assumed the task would be done much faster than 51 seconds, but sadly, that wasn't the case. Even going up to 1,000,000 took a considerable amount of time (didn't time it, though)

#include <iostream>
#include <vector>
using namespace std;

void main()
{
    vector<int> tosieve = {};        
    for (int i = 2; i < 1000001; i++) 
    {                                       
        tosieve.push_back(i);               
    }                                       
        for (int j = 0; j < tosieve.size(); j++)
        {
            for (int k = j + 1; k < tosieve.size(); k++)
            {
                if (tosieve[k] % tosieve[j] == 0)
                {
                    tosieve.erase(tosieve.begin() + k);
                }
            }
        }
    //for (int f = 0; f < tosieve.size(); f++)
    //{
    //  cout << (tosieve[f]) << endl;
    //}
    cout << (tosieve.size()) << endl;
    system("pause");
}

Is it the repeated referencing of the vectors or something? Why is this so slow? Even if I'm completely overlooking something (could be, complete beginner at this :I) I would think that finding the primes between 2 and 1,000,000 with this horrible inefficient method would be faster than my original way of finding them from 2 to 10,000,000.

Hope someone has a clear answer to this - hopefully I can use whatever knowledge is gleaned in the future when optimizing programs using a lot of recursion.

Answer 1

Most of vector operations, including erase() have a O(n) linear time complexity.

Since you have two loops of size 10^6, and a vector of size 10^6, your algorithm executes up to 10^18 operations.

Qubic algorithms for such a big N will take a huge amount of time.
N = 10^6 is even big enough for quadratic algorithms.

Please, read carefully about Sieve of Eratosthenes. The fact that both full search and Sieve of Eratosthenes algorithms took the same time, means that you have done the second one wrong.