原始题目

Problem D. Euler Function

• Time Limit: 2000/1000 MS (Java/Others)
  
• Memory Limit: 524288/524288 K (Java/Others)
• Total Submission(s): 150
  
• Accepted Submission(s): 136

Problem Description

In number theory, Euler's totient function \(\varphi(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\leq k\leq n\) for which the greatest common divisor \(\gcd(n, k)\) is equal to \(1\).

For example, \(\varphi(9) = 6\) because \(1,2,4,5,7\) and \(8\) are coprime with \(9\). As another example, \(\varphi(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 \(\varphi(n)\) is a composite number.

Input

The first line of the input contains an integer \(T(1\leq T\leq100000)\), denoting the number of test cases. In each test case, there is only one integer \(k(1\leq k\leq 10^9)\).

Output

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

Sample Input

2
1
2

Sample Output

5
7

Source

2018 Multi-University Training Contest 3

Recommend

chendu

题目大意

求第k个正整数n，其欧拉函数\(\varphi(n)\)为合数。

解题思路

• 数论题
• 手写一下，发现数稍微大便全是合数。反向考虑\(\varphi(n)\)为质数。
• 已知\(\varphi(n) = p\_1^{k\_1-1}(p\_1-1)p\_2^{k\_2-1}(p\_2-1)\cdots\)，其中\(\gcd(p\_1, p\_2 \cdots)=1\)。分情况讨论：
  • 情况1：\(n\)为\(p^k\)形式，即只有一个质因子。
  • 子情况1.1：该质因子为\(2\)，那么要使\(\varphi(n)\)为质数，则\(p^{k-1}\)为质数，很明显\(k=1,2\)，所以该情况下\(n\)只能为\(2,4\)
  • 子情况1.2：该质因数不为\(2\)，那么要使\(\varphi(n)\)为质数，\(p-1\)也得为质数，很明显成立的只有\(3\)（相邻两个数均为质数）
  • 情况2：\(n\)由两个质因子构成。
  • 子情况1.1：其中一个为\(2\)，由于另一个会贡献一个\(2\)，要使\(\varphi(n)\)为质数,则\(2\)质因数指数只能为\(1\)，另一质因数只能为\(3\)，指数只能为\(1\)。
  • 子情况2.2：均不为\(2\)，那么两个质因子各贡献一个\(2\)，那么\(\varphi(n)\)一定为4的倍数，不为质数。
• 当\(n=1,2,3,4,6\)时，\(\varphi(n)\)为质数。

# 解题代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int T;
	long long k;
	cin>>T;
	while(T--)
	{
		cin>>k;
		if(k==1) cout<<5<<endl;
		else cout<<k+5<<endl;
	}
	return 0;
}

# 收获与反思 - 数论先推前几项再分析 - 掌握欧拉函数的计算方法和性质。