题目70：考察φ(n)是n的一个排列的n值
Totient permutationEuler's Totient function, φ(n) , 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 < , 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 < ，并且 φ(n) 是 n 的一个排列的那些 n 中，使得 n/φ(n) 取到最小的 n 是多少？
有了第69题的算法程序，这题就是送分题了把{:5_95:} 这题唯一的问题是上限提升了10倍，到10的7次方，所以花的时间就多了好多，好在还能算……
8319823 1.0007090511248113
Time:133.215 sec
from time import clock
start = clock()
def getPrime(n):
primes = *n
primes, primes = False, False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i*i,n,i):
primes = False
primelist = []
for (k, trueprime) in enumerate(primes):
if trueprime:
primelist.append(k)
return primelist
def philist(n):
primelist = getPrime(n)
PHI = *(n+1)
PHI, PHI = -1, 1
for eachprime in primelist:
PHI = eachprime - 1
for i in range(len(primelist)):
p = primelist
for k in range(p*p,n+1,p):
PHI = PHI*(p-1)
for j in range(p*p,n+1,p*p):
PHI = PHI*p
return PHI
plist = philist(10000000)
minn, minnphi = 2, 2
for i in range(2,10000000):
if sorted(list(str(i))) == sorted(list(str(plist))):
if i/plist < minnphi:
minnphi = i/plist
minn = i
print (minn, minnphi)
end = clock()
print ('Time:%.3f sec' % (end-start)) 303963552391
Time:4.211 sec
from time import clock
start = clock()
def getPrime(n):
primes = *n
primes, primes = False, False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i*i,n,i):
primes = False
primelist = []
for (k, trueprime) in enumerate(primes):
if trueprime:
primelist.append(k)
return primelist
def philist(n):
primelist = getPrime(n)
PHI = *(n+1)
for eachprime in primelist:
PHI = eachprime - 1
for i in range(len(primelist)):
p = primelist
for k in range(p*p,n+1,p):
PHI = PHI*(p-1)
for j in range(p*p,n+1,p*p):
PHI = PHI*p
return PHI
plist = philist(1000000)
print(sum(plist))
end = clock()
print ('Time:%.3f sec' % (end-start)) # encoding:utf-8
# 寻找phi(n)为n的排列的数
from time import time
def getPrimes(n):
primes = * n
primes, primes = False, False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i * i, n, i):
primes = False
return
# 学习jerryxjr1220代码
def getPhis(N):
l_primes = getPrimes(N)
l_phis = * (N + 1)
for x in l_primes:
l_phis = x - 1
for p in l_primes:
for x in range(p * p, N + 1, p):
l_phis = l_phis * (p - 1)
for y in range(p * p, N + 1, p * p):
l_phis = l_phis * p
return l_phis
def euler070(N=10000000):
l_phis = getPhis(N)
minphi, num = 1.1, 0
for i in range(2, N + 1):
if sorted(list(str(i))) == sorted(list(str(l_phis))):
if i / l_phis < minphi:
minphi, num = i / l_phis, i
print(minphi, num)
if __name__ == '__main__':
start = time()
euler070()
print('cost %.6f sec' % (time() - start))
1.0007090511248113 8319823
cost 58.685000 sec P = []
L = list(range(10000000))
for i in range(2, len(L)):
if L == i:
P.append(i)
L = i - 1
for p in P:
if i * p >= len(L):
break
if i % p == 0:
L = L * p
break
L = L * (p - 1)
print(min(map(lambda x: / x, x], filter(lambda x: sorted(str(x)) == sorted(str(x)), list(enumerate(L))))))
https://github.com/devinizz/project_euler/blob/master/page02/70.py 8319823
Process returned 0 (0x0) execution time : 32.889 s
Press any key to continue.
思路相同的c++实现
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int M = 1e7;
int ct = 0;
bool prime;
int factor;
int phi = {0};
void euler_sieve(){
prime = false;
for (int i = 2;i <= M;i++) prime = true;
for (int i = 2;i <= M;i++){
if (prime) {factor[++ct] = i;phi = i-1;}
for (int j = 1;j <= ct && i*factor < M;j++){
prime] = false;
if (i % factor == 0) break;
}
}
}
void ini(){
for (int i = 2;i <= sqrt(M);i++){
if (prime){
for (int j = i;j*i <= M;j++)
if (j % i == 0) phi = phi * i;
else phi = phi * (i-1);
}
}
}
void parse(vector<int> & v,int x){
while(x){
v.push_back(x % 10);
x /= 10;
}
}
int main(){
euler_sieve();ini();
int ans;
double minn = M;
for (int n = 2;n < M;n++){
vector<int> a,b;
double t = n / (double)phi;//cout << t << endl;
parse(a,n); parse(b,phi);
sort(a.begin(),a.end());
sort(b.begin(),b.end());
if (a == b){
if (t < minn){minn = t; ans = n;}
}
}
cout << ans << endl;
return 0;
}
本帖最后由 永恒的蓝色梦想 于 2021-2-20 20:37 编辑
C++ 133ms#include<iostream>
#include<vector>
#include<limits>
#include<cstring>
using namespace std;
template<size_t size, typename T>
void euler_sieve(bool(&is_prime), vector<T>& primes, T(&phi)) {
T i, k;
memset(is_prime, -1, size);
is_prime = is_prime = 0;
for (i = 2; i < size; i++) {
if (is_prime) {
primes.push_back(i);
phi = i - 1;
}
for (T j : primes) {
k = i * j;
if (k >= size) {
break;
}
is_prime = false;
if (!(i % j)) {
phi = phi * j;
break;
}
phi = phi * (j - 1);
}
}
}
bool is_permutation(unsigned int a, unsigned int b)noexcept {
unsigned int t;
unsigned char digits = { 0 };
while (a) {
t = a;
a /= 10;
digits++;
}
while (b) {
t = b;
b /= 10;
digits--;
}
return !((*(unsigned long long*)(&digits)) | (*(unsigned short*)(&digits)));
}
int main() {
ios::sync_with_stdio(false);
constexpr unsigned int UPPER_BOUND = 10000000;
static bool is_prime;
static unsigned int phi;
vector<unsigned int> primes;
double min_div = numeric_limits<double>::max(), div;
unsigned int min_n = 0, n;
euler_sieve(is_prime, primes, phi);
for (n = 2; n < UPPER_BOUND; n++) {
div = (double)n / phi;
if (div < min_div && is_permutation(n, phi)) {
min_div = div;
min_n = n;
}
}
cout << min_n << endl;
return 0;
}
页:
[1]