算法1

(暴力枚举) $O(n^2)$

通过埃式筛的重复计算，就可以很容易解出这题，时间复杂度是埃式筛的logn倍

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[1000010];
int b[1000010];
int main()
{
  int n;
  cin>>n;
  for(int i=2;i<=n;i++){
    if(b[i]==0){
        int j=1;
        ll sum=1;
        for(int j=2;j<=n&&i*j<=n;j++)
        {


                int t=i*j;
                while(t&&t%i==0){
                    t/=i;
                  //  cout<<i*j<<endl;
                    sum++;
                }

            b[i*j]=1;
           // cout<<i*j<<endl;

        }

        printf("%d %d\n",i,sum);
    }
  }


    return 0;
}