链接：https://www.nowcoder.com/acm/contest/141/H
来源：牛客网
Input has only one line containing a positive integer N.
1 ≤ N ≤ 10
7
Output one line containing a non-negative integer indicating the number of diff-prime pairs (i,j) where i, j ≤ N
3
2
5
6
题意：输入一个n，n里面选一对数，满足%7D)
这两个式子的数都是素数，不同顺序也算是另一对
思路：我们会发现i，j都是素数的话，那么最大公约数为1，那么肯定是一对，然后我们再想想（6，10），（6，9）...都是
那么他们有什么规律呢，就是我们要使除了两个数的最大公约数之后都是素数，那么说明两个数分解之后就应该是 a=(素数)x*n b=(素数)y*n
n是最大公约数那么其他的满足这个条件对数其实就是一个素数对，同时乘以一个数那么也是，例如（2，3）那么（4，6）（6，9）（8，12）都是
满足条件的数，那么我们应该怎么计算呢，下面我们讲个例子
首先想10以内有几个3的倍数呢，10/3=3个，这是常识
那么我们就来计算，由所有的素数对扩展
10以内的所有对，因为我们首先应该找出素数对，所以我们应该是遍历所有的素数，
第一个 2 ：10/2=5，10以内有5个2的倍数，我们再看2的前面有没有素数，没有，不计算
第二个 3 ：10/3=3 ....3 6 9,前面有素数2，我们就可以找到素数2组成（2，3），然后两个数同时乘以2，3，因为前面的
小，所以我们始终能在6 9 前面找到4 6组成（4，6）（6，9）
第三个：5...
第四个：7...
下面看代码实现
#include<bits/stdc++.h> #define fi first #define ll long long #define pll pair<int,int> #define se second #define mod 1000000007 using namespace std; const int maxn = 10000010; bool isPrime[maxn]; ll prime[maxn]; ll sum[maxn]; ll add[maxn]; ll total=0; map< pll ,int> mp; void makePrime2()//筛法找出所有的素数 { memset(isPrime,true,sizeof(isPrime)); memset(prime,0,sizeof(prime)); sum[1]=0; for(int i=2; i<maxn; i++) { if(isPrime[i]) { prime[total++]=i; sum[i]=sum[i-1]+1;//用于存当前位置有多少个素数 } else sum[i]=sum[i-1]; for(int j=0; j<total && i*prime[j]<maxn; j++) { isPrime[i*prime[j]]=false; if(i%prime[j]==0) break; } } } int main() { makePrime2(); ll n; scanf("%lld",&n); ll ans=0; for(int i=0; i<total&&prime[i]<=n; i++) { int p=n/prime[i];//找出n以内有多少个素数prime[i]的倍数 ans+=(sum[prime[i]]-1)*p;//-1因为本身这个素数不算，然后和前面的素数进行匹配与扩展 } printf("%lld\n",ans*2); }
原文：https://www.cnblogs.com/Lis-/p/9374618.html