HDU 6322 Euler Function （欧拉函数的求法） 1/5

题目链接：https://vjudge.net/problem/HDU-6322

题意：给一个数k，求第k小的n值，n满足φ(n)是合数。

欧拉函数定义：小于n的正整数中与n互质的数的数目就是φ(n)的值，n为正整数。

对欧拉函数打表发现，只有1 2 3 4 6 的欧拉函数值不是合数，则满足要求的第1小对应的n值为5，其余则为k+5；

代码：

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<ctype.h>
using namespace std;

int phi(int x)//求欧拉函数
{
    int i,j;
    int num = x;
    for(i = 2; i*i <= x; i++)
    {
        if(x % i == 0)
        {
            num = (num/i)*(i-1);
            while(x % i == 0)
            {
                x = x / i;
            }
        }
    }
    if(x != 1)
        num = (num/x)*(x-1);
    return num;
}

int main()
{
    int n=0;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(n==1)
            printf("5\n");
        else
            printf("%d\n",n+5);
    }


    return 0;
}