Problem D. Euler Function（欧拉函数的性质）

Problem Description

In number theory, Euler's totient function φ(n) counts the positive integers up to a given integer n that are relatively prime to n. It can be defined more formally as the number of integers k in the range 1≤k≤n for which the greatest common divisor gcd(n,k) is equal to 1.
For example, φ(9)=6 because 1,2,4,5,7 and 8 are coprime with 9. As another example, φ(1)=1 since for n=1 the only integer in the range from 1 to n is 1 itself, and gcd(1,1)=1.
A composite number is a positive integer that can be formed by multiplying together two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. So obviously 1 and all prime numbers are not composite number.
In this problem, given integer k, your task is to find the k-th smallest positive integer n, that φ(n) is a composite number.

Input

The first line of the input contains an integer T(1≤T≤100000), denoting the number of test cases.
In each test case, there is only one integer k(1≤k≤109).

Output

For each test case, print a single line containing an integer, denoting the answer.

Sample Input

2 1 2

Sample Output

5 7

这道题我最初没有头绪，所以想看看有没有什么规律，尝试for循环从1~1000，找里面满足第k小的n为几。发现一个很神奇的事情：

当k=1时，n=5，当k>1时，n=k+5；

打表代码如下：

#include<iostream>
using namespace std;
#define max 1005
int prime[max];
//素数筛
void isprime() {
	for (int i = 2; i <= max; i++) {
		if (!prime[i])prime[++prime[0]] = i;
		for (int j = 1; j <= prime[0]; j++) {
			if (prime[j] * i > max)break;
			prime[prime[j] * i] = 1;
			if (i % prime[j] == 0)break;
		}
	}
	return;
}
int func(int n) {
	if (n == 1) return 1;
	int ans = 1;
	for (int i = 0; i < prime[0]; i++) {
		int p = prime[i];
		if (n % p == 0) {
			ans *= (p - 1);
			n /= p;
			while (n % p == 0) {
				ans *= p;
				n /= p;
			}
		}
		if (n == 1)return ans;
	}
	return ans * (n - 1);
}
bool func2(int x) {
	int n = sqrt(x);
	for (int i = 2; i <= n; i++) {
		if (x % i == 0)return true;
	}
	return false;
}
int main() {
	//int t;
	//cin >> t;
	isprime();
	int ans = 0;
	for (int i = 1; i <= 100; i++) {
		
		if (func2(func(i))) {
			ans++;
			cout << "第" << ans << "个满足条件的n为" << i << endl;
		}
	}
	/*while (t--) {
		int k;
		cin >> k;
	}*/

	return 0;
}

既然1000以内完全符合这个条件，那么大胆猜测1~10^9应该也是满足条件的，所以代码就很简单了。

AC代码如下：

#include<iostream>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int k;
        cin >> k;
        if (k == 1)cout << 5 << endl;
        else cout << k + 5 << endl;
    }
}