为什么埃氏筛会超时 不理解求改

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int prime[1001000],st[1000100],cnt=0;
void shai(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            prime[++cnt]=i;
            for(int j=i;j<=n;j+=i) st[j]=true;
        }
    }
}
int ans[1000010];
int main()
{
    int n;
    scanf("%d",&n);
    shai(n);
// 10
// 2 2 2 2 2 2 2 2
// 3 3 3 3 
// 5 5  
// 7   
//	for(int i=1;i<=cnt;i++)
//	{
//		cout<<prime[i]<<endl;
//	}
	int cnt2=0;
    for(int i=1;i<=n;i++)
    {
		int x=i;
    	for(int j=1;j<=cnt&&x!=1;j++)
    	{
			while(x%prime[j]==0) ans[prime[j]]++,x/=prime[j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(ans[i]!=0)
		printf("%d %d\n",i,ans[i]);
	}
    return 0;
}