ACM-ICPC 2018南京赛区网络预赛 J Sum（线性筛）
一个无平方因子的整数是指其不能被任何大于1的平方数整除的整数。例如6=2×3是一个无平方因子的数；但12=2²×3则不是一个无平方因子的数目因它含有2²这个平方因子。
某些整数可以分解为两个无平方因子数目相乘的形式，并且可能存在多种不同的分解方式。
例如6=1×6=6×1=2×3=3×2，
其中n=ab和n=ba被视为不同的分解情况当a≠b时。
设f(n)表示满足n=ab的所有分解情况数目，
其中a和b均为无平方因子数目，
我们的目标就是计算∑_{i=1}^n f(i).
Input
The initial line includes an integer T(T\le 20), which represents the count of test cases.
For each test case, there first line has a integer n(n \le 2\cdot 10^7)n(n≤2⋅107).
Output
For each test case, print the answer \sum_{i = 1}^n f(i)∑i=1nf(i).
Hint
\sum_{i = 1}^8 f(i)=f(1)+ \cdots +f(8)∑i=18f(i)=f(1)+⋯+f(8)
=1+2+2+1+2+4+2+0=14=1+2+2+1+2+4+2+0=14.
样例输入复制
样例输出复制
题目来源
第20届ACM-ICPC国际 Collegiate Programming Contest（中国）南京赛区网络预赛
题意：定义f[i]为i可分割成两个非平方因数之数量（考虑顺序的情况），并计算其前缀和。
思路：对于任意整数n≥1来说，在其素因子分解中可表示为n = a₁{p₁}·a₂{p₂}·…·aₙ^{pₙ}的形式。若其中存在某个指数p_i满足p_i ≥ 3，则函数f(n)的值为零；反之则f(n)等于2的（所有指数p_i=1的情况之和）次幂。该性质可以通过素因子分解的线性筛选法来证明。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e7+10;
bool check[maxn];
int prime[maxn];
ll f[maxn];
int tot=0;
int main(){
check[1] = 1;
f[1] = 1;
int num;
for(int i=2;i<maxn;i++){
if(check[i]==0){ //prime
prime[tot++]=i;
f[i] = 2;
}
for(int j = 0;j<tot&&(ll)i*prime[j]<maxn;++j)
{
num = i*prime[j];
check[num] = 1;
if(i%prime[j])
{
f[num] = f[i]*2;
}
else if((ll)i%(prime[j]*prime[j])==0)
{
f[num] = 0;
}
else
{
f[num] = f[num/prime[j]/prime[j]];
break;
}
}
}
for(int i = 2;i<maxn;i++)
f[i] += f[i-1];
int t;
int n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%lld\n",f[n]);
}
}