洛谷 P2043质因子分解 题解

题目传送门

N的范围很小，所以使用O(n²)的算法就能过啦！

#include<bits/stdc++.h>
using namespace std;
int a[10001],n;
int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        int i2=i;
        for(int j=2;j<=i;j++)
            while(i2%j==0){a[j]++; i2/=j;} 
    }
    for(int i=1;i<=10000;i++)
        if(a[i]!=0) cout<<i<<" "<<a[i]<<endl;
    return 0;
}