P1403 [AHOI2005] 约数研究

题目分析

这一题要约数的个数，但是数据范围又有 $10^6$ 所以暴力枚举肯定不行。再看，这是一个数论题，所以就有两种方法：数学方法和枚举优化。

数学方法（本篇讲解）

质数：除以任何一个数（除了一和本身）都不是整数。 所以就有枚举除以的数即可

#include<iostream>
using namespace std;
int n,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)ans+=n/i;
    cout<<ans<<endl;
    return 0;
}

枚举优化

打表，主要是质数。（不讲了，请自行体会）