fork download
copy 
  1. import itertools
  2. import functools
  3.  
  4. # n以下の素数リスト
  5. # エラトステネスのふるい
  6. # 参考:http://q...content-available-to-author-only...a.com/neko_the_shadow/items/4ebad619564a48f5a97f
  7. def primes(n):
  8.     plist = [i for i in range(n + 1)]
  9.     plist[0] = 0
  10.     plist[1] = 0
  11.  
  12.     for p in plist:
  13.         if p == 0:
  14.             continue
  15.         if p * p > n:
  16.             return [p for p in plist if p != 0]
  17.  
  18.         for a in range(2 * p, n + 1, p):
  19.             plist[a] = 0
  20.  
  21.  
  22. # xとyが置換可能
  23. def replaceable(x, y):
  24.  
  25.     if sorted(str(x)) == sorted(str(y)):
  26.         return True
  27.  
  28.     return False
  29.  
  30.  
  31. N = 10000000
  32. plist = primes(4000)
  33.  
  34. min = float('inf')
  35. min_n = float('inf')
  36. for l in itertools.combinations(plist, r = 2):
  37.     # nは選んだ2つの素数の積
  38.     n = int(l[0]) * int(l[1])
  39.     if n > N:
  40.         continue
  41.  
  42.     # φ(n)
  43.     phi = (int(l[0]) - 1) * (int(l[1]) - 1)
  44.  
  45.     if min > (n / phi) and replaceable(n, phi):
  46.         min = n / phi
  47.         min_n = n
  48.  
  49. print(min_n)
  50.  
Success #stdin #stdout 0.24s 27720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8319823
https://ideone.com/IxvPb3
language:
Python 3 (python  3.9.5)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!