洛谷P1403 [AHOI2005] 约数研究
题目链接：P1403 [AHOI2005] 约数研究 - 洛谷 | 计算机科学教育新生态
题目难度：普及一
题目分析：本题很明显是要你求从i到n的质因数个数之和，如果采用暴力肯定是超时的，故我的想法是采用埃氏筛法来求时间复杂度为（nlog n)1s能跑完.
下面奉上代码部分：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int primes[N];
int n;
int ans;
int get_divisors(int n)
{
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j += i)
primes[j]++;
ans += primes[i];
}
return ans;
}
ll read()
{
ll s=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9')
{
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
int main() {
n = read();
cout<<get_divisors(n)<<endl;
return 0;
}