HDU - 6322 - Problem D. Euler Function 【欧拉函数 + 规律】题解

叁歲伎倆 2021-07-25 00:07 338阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

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 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

### 2.代码 ###

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