(Problem 70)Totient permutation

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6. The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Find the value of n, 1  n  107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
제목 대의:
오라 함수φ(n) (때로는phi 함수라고도 부른다) n보다 작은 숫자에서 n과 상호작용하는 숫자의 개수를 계산할 수 있다.예를 들어 1,2,4,5,7,8은 모두 9보다 작고 9와 상호작용하기 때문에φ(9)=6.
숫자 1은 모든 정수와 상호작용한다고 여겨지기 때문에φ(1)=1.
재미있는 것은,φ(87109) = 79180, 87109가 79180의 배열임을 알 수 있다.
1 n 107 및φ(n)은 n의 배열된 n들 중에서 n/φ(n) 가장 작은 n을 찾으면 얼마입니까?

//（Problem 70）Totient permutation

// Completed on Tue, 18 Feb 2014, 11:06

// Language: C11

//

//  （C）acutus   (mail: [email protected]) 

//  ：http://www.cnblogs.com/acutus/

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

#include<stdbool.h>



#define N 10000000



int phi[N];     // 



int cmp(const void * a, const void * b)

{

    return (*(char *)a - *(char *)b);

}



void genPhi(int n)// n (n-1 )

{

    int i, j, pNum = 0 ;

    memset(phi, 0, sizeof(phi)) ;

    phi[1] = 1 ;

    for(i = 2; i < n; i++)

    {

        if(!phi[i])

        {

            for(j = i; j < n; j += i)

            {

                if(!phi[j])

                    phi[j] = j;

                phi[j] = phi[j] / i * (i - 1);

            }

        }

    }

}



int fun(int n)  // n 

{

    return (log10(n *1.0) + 1);

}



bool compare(int n, int m)  // 

{

    int i, L1, L2;

    char from[10], to[10];

    sprintf(from, "%lld", m);

    sprintf(to, "%lld", n);

    L1 = strlen(from);

    L2 = strlen(to);

    qsort(from, L1, sizeof(from[0]), cmp);

    qsort(to, L2, sizeof(to[0]), cmp);

    return !strcmp(from, to);

}



void solve()

{

    int i, j, count, k;

    double min, t;

    min = 10.0;

    for(i = 2; i < N; i++) {

        if((fun(i) == fun(phi[i])) && compare(i, phi[i])) {

            t = i * 1.0 / phi[i];

            if(t < min) {

                min = t;

                k = i;

            }

        }

    }

    printf("%d
", k);

}



int main()

{

    genPhi(N);

    solve();

    return 0;

}

Answer:
8319823