Linear sieve method (prime sieve)

One O(n) The algorithm of filtering prime number with time complexity ：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1000000;
int primes[N],cnt;//primes Array storage prime 
int minp[N];// Store the minimum quality factor 
bool st[N];// Is it currently filtered 
void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])minp[i]=i,primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++)// Screening prime 
        {
            st[primes[j]*i]=true;
            minp[primes[j]*i]=primes[j];//primes[j]*i The minimum quality factor of is priems
            if(i%primes[j]==0)break;//primes No more than i The minimum quality factor of 
        }
    }
}
int main()
{
    get_primes(10000);
    for(int i=2;i<20;i++)
    {
        cout<<primes[i]<<" "<<minp[i]<<endl;
    }
}