牛客网暑期ACM多校训练营（第三场）# E-Sort String （next数组的应用）H Diff-prime Pairs

题目链接：https://www.nowcoder.com/acm/contest/141/H

题目大意：两个数i和j，如果和是两个互质的数的话，就记为一个质数对。

问1-n以内有多少个质数对，注意（i，j）和（j，i）记为两对。

题目思路：首先素数筛预处理出所有的质数，然后枚举素数对，如果大的素数的k倍小于n的话，那么小的素数的k倍也小于n。

所以我们枚举的时候，假设左边比右边的素数要小，每次对于一个素数，找比他小的素数有多少个，然后乘上它能最多变大多少倍即可。

注意最后结果乘以2即可。

WA点， for(int i=2;prime[i]<=n&&i<=prime[0];i++)

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e7;
int prime[maxn+10];
void getprime()
{
    memset(prime,0,sizeof prime);
    for(int i=2;i<=maxn;i++)
    {
        if(!prime[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++)
        {
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int n;
int main()
{
    getprime();
    while(~scanf("%d",&n))
    {
        long long  ans=0;
        for(int i=2;prime[i]<=n&&i<=prime[0];i++)
        {
            ans+=1ll*(i-1)*(n/prime[i]);
        }
        printf("%lld\n",ans*2);
    }
    return 0;
}