Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal tonwhich are relatively prime ton. 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 ofn, 1 <n< 107, for which φ(n) is a permutation ofnand the ration/φ(n) produces a minimum.
#include <iostream>#include <map>using namespace std;int getEuler(int n){int m = n;int p = 2;int k = 0;while (p*p <= n){k = 0;while (n%p == 0){n /= p;k++;}if (k >= 1)m = m / p*(p – 1);p++;}if (n > 1)m = m / n*(n – 1);return m;}map<int, int> getnum(int n){map<int, int>mp;while (n){mp[n % 10]++;n /= 10;}return mp;}bool isPermutation(int a,int b){map<int, int>an = getnum(a);map<int, int>bn = getnum(b);if (an == bn)return true;elsereturn false;}int main(){double mine = 10000000.0;int num;for (int i = 2; i <= 10000000; i++){int b = getEuler(i);double tmp = i*1.0 / b;if (isPermutation(i,b)){//cout << i << " " << b << endl;if (tmp < mine){mine = tmp;num = i;}}}cout << num << " " << mine << endl;system("pause");return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
谦受益，满招损。
