# 牛客多校 2018 第三场 H Diff-prime Pairs（素数）

## Diff-prime Pairs

• 时间限制：C/C++ 1秒，其他语言2秒
• 空间限制：C/C++ 262144K，其他语言524288K
• 64bit IO Format: %lld

### 题目描述

Eddy has solved lots of problem involving calculating the number of coprime pairs within some range. This problem can be solved with inclusion-exclusion method. Eddy has implemented it lots of times. Someday, when he encounters another coprime pairs problem, he comes up with diff-prime pairs problem. diff-prime pairs problem is that given N, you need to find the number of pairs (i, j), where $\frac{i}{gcd(i, j)}$ and $\frac{j}{gcd(i, j)}$ are both prime and i ,j ≤ N. gcd(i, j) is the greatest common divisor of i and j. Prime is an integer greater than 1 and has only 2 positive divisors.
Eddy tried to solve it with inclusion-exclusion method but failed. Please help Eddy to solve this problem.
Note that pair (i1, j1) and pair (i2, j2) are considered different if i1 ≠ i2 or j1 ≠ j2.

### 输入描述:

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

### 链接

https://www.nowcoder.com/acm/contest/141/H

### 题解

$\frac{i}{gcd(i, j)} / \frac{j}{gcd(i, j)} = \frac{i}{j}$，当$\frac{x}{y} = \frac{i}{j}$时，$\frac{x}{y}*t$也符合条件，$1<=t<=n/max(x, y)$。

### 代码

• 代码长度：721 运行时间： 125 ms 占用内存：12896K  运行结果：答案正确
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 10;
bool isComp[maxn] = {false};
int P[maxn] = {0};
int Pcnt = 0;

void sizve(int n) // 筛法得到n以内的质数
{
for (int i = 2; i <= n; ++i)
{
if (!isComp[i])
P[Pcnt++] = i;
for (int j = 0; j < Pcnt && i * P[j] <= n; ++j)
{
isComp[i * P[j]] = true;
if (i % P[j] == 0)
break;
}
}
}

int main()
{
int n;
scanf("%d", &n);
sizve(n);
ll ans = 0;
for (int i = 1; i < Pcnt; ++i) // 从第二个质数3开始配对
ans += n / P[i] * i;
ans *= 2;
printf("%lld\n", ans);
return 0;
}

The end.
2018-08-07 星期二