论

质因子分解

额…………

好吧，我承认！

这道实际用时只有10min。（我真不是故意不写点！？）

下面是代码：

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

这题主要思想是：

开个数组，存质数个数，先定义为全为0，以便输出时判断，然后1、2、3...、n分别求质因子，不用判断是不是质数，因为每个质因子我们都一直除，直到不能再除，以后也不会出现可以除的数是此数的倍数了，相当于已经筛掉了。

$比赛决策失误了$ ,走向了高精度这条错误的道路。