链接：https://www.jisuanke.com/contest/1555?view=challenges
题意：一个数可以用a*b表示且a,b不是一个平方数，这个数有几种a*b的表达方式，则这个数的价值就为几，输入一个n求前缀和
思路：一个数要么是素数，要么是素数的倍数。(1例外答案就是1)（下面每个数的价值用sum[]表示）
这里用类似素数筛的方法。预处理，每个数都遍历一遍。
用vis标记素数和合数（1为素数，0为合数）
首先，先明确一个条件，任何合数都能表示成一系列素数的积。
然后利用了每个合数必有一个最小素因子，每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。
代码中体现在：
if(i%prime[j]==0)break;
prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。
因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。（这样可以节约时间，时间复杂度也降为O(n)）
在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,prime[j]必定是prime[j]*i的最小因子。
摘抄于http://www.mamicode.com/info-detail-662432.html
所以有两种情况：
1.当i为素数时，sum为2.
2.当处理合数时,i*prime(此时，i*prime的最小素因子就是prime）分两种情况
a. i%prime！=0（i不是prime的倍数）那么，sum[i*prime]=sum[i]*2;
因为，i可以用a*b表示，a,b都不是prime的倍数，i*prime就可以用（a*prime ）*b,和a* (prime*b)表示（所以是两倍）
b. i%prime==0,又分两种情况：（break,就是上面讲的线性时间复杂度）
一.i%(prime*prime)==0,则sum[i*prime]=0;因为i如果用a*b表示，a是prime的倍数,b也是prime平方的倍数。所以i*prime其中
有一因子一定是平方数。
二.i%(prime*prime)!=0,则sum[i*prime]=sum[i]/2，因为sum[i*prime]=sum[i/prime]=sum[i]/2.
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=2e7+10; ll ans[maxn];//前缀和 int vis[maxn],prime[maxn],sum[maxn]; void init() { memset(vis,0,sizeof(vis)); memset(ans,0,sizeof(ans)); int pos=0;//素数的个数 ans[1]=1; for(int i=2;i<maxn;i++) { if(!vis[i])//标记素数 { prime[pos++]=i; sum[i]=2; } for(int j=0;j<pos&&i*prime[j]<maxn;j++) { vis[i*prime[j]]=1;//标记合数 if(i%prime[j]) sum[i*prime[j]]=sum[i]*2; else { if(i%(prime[j]*prime[j])==0) sum[i*prime[j]]=0; else sum[i*prime[j]]=sum[i]/2; break;//重点，当i%prime[j]时break,线性时间 } } } for(int i=2;i<maxn;i++) ans[i]=ans[i-1]+sum[i]; } int main() { init(); int t,n; cin>>t; while(t--) { cin>>n; cout<<ans[n]<<endl; } return 0; }