fork(1) download
copy 
  1. from itertools import combinations
  2.  
  3.  
  4. def primal_numbers(n):
  5.     a = [True for i in range(n + 1)]
  6.     a[0] = False
  7.     a[1] = False
  8.     out = []
  9.     for i in range(2, n + 1):
  10.         if not a[i]:
  11.             continue
  12.         out.append(i)
  13.         for j in range(i, n + 1, i):
  14.             a[j] = False
  15.     return out
  16.  
  17.  
  18. def factorize_number(n, primlist, primset):
  19.     out = []
  20.     while n not in primset:
  21.         for p in primlist:
  22.             if n % p == 0:
  23.                 out.append(p)
  24.                 n //= p
  25.                 break
  26.         else:
  27.             break
  28.     if not out:
  29.         return None
  30.     if n != 1:
  31.         out.append(n)
  32.     return out
  33.  
  34.  
  35. def product(*a):
  36.     r = 1
  37.     for x in a:
  38.         r *= x
  39.     return r
  40.  
  41.  
  42. def step_count(step, k):
  43.     shift = step % k
  44.     a, r = 0, 0
  45.     while True:
  46.         r += 1
  47.         a += shift
  48.         if a >= k:
  49.             a -= k
  50.         if a == 0:
  51.             return r
  52.  
  53.  
  54. def check_result_set(value, mset):
  55.     for i in mset:
  56.         if value % i != 0:
  57.             return False
  58.     return True
  59.  
  60.  
  61. def find_divisible_by_set(mset, simple=False, debug=False):
  62.     plist = primal_numbers(max(mset))
  63.     pset = set(plist)
  64.  
  65.     step_mults = mset & pset
  66.     step = product(*list(step_mults))
  67.     if debug:
  68.         print('STEP MULT', sorted(step_mults))
  69.         print('STEP', step)
  70.  
  71.     ax = set()
  72.     for j in mset:
  73.         f = factorize_number(j, plist, pset)
  74.         if f is None:
  75.             continue
  76.         ax.update(f)
  77.         for k in range(2, len(f)):
  78.             for comb in combinations(f, k):
  79.                 ax.add(product(*comb))
  80.     if debug:
  81.         print('ALL POSSIBLE FACTORIZATION MULTIPLIERS', list(reversed(sorted(list(ax)))))
  82.     ax = mset - ax
  83.     if debug:
  84.         print('INVERTED', list(reversed(sorted(list(ax)))))
  85.     ax = ax - step_mults
  86.     if debug:
  87.         print('REMOVED PRIMALS (THEY ARE ALL INCLUDED IN STEP)', list(reversed(sorted(list(ax)))))
  88.  
  89.     discards = []
  90.     for k in ax:
  91.         if step % k == 0:
  92.             discards.append(k)
  93.     for k in discards:
  94.         ax.discard(k)
  95.     if debug:
  96.         print('FILTERED BY STEP MOD', list(reversed(sorted(list(ax)))))
  97.  
  98.     max_result = product( *list(ax | step_mults) )
  99.     assert check_result_set(max_result, mset)
  100.     if debug:
  101.         print('WORST CASE RESULT', max_result)
  102.         print('ITER COUNT', max_result // step)
  103.  
  104.     ax = list(reversed(sorted(list(ax))))
  105.  
  106.     if simple:
  107.         i = step
  108.         while True:
  109.             for k in ax:
  110.                 if i % k != 0:
  111.                     break
  112.             else:
  113.                 break
  114.             i += step
  115.         if debug:
  116.             print('RESULT', i)
  117.         return i
  118.     else:
  119.         sset = set()
  120.         for k in ax:
  121.             # print(k, step % k, step_count(step, k))
  122.             sset.add(step_count(step, k))
  123.         if debug:
  124.             print('STEPS SET', sorted(list(sset)))
  125.             print('RECURSING IN...')
  126.         fx = find_divisible_by_set(sset, simple=True)
  127.         if debug:
  128.             print('RECURSING OUT...')
  129.         return step * fx
  130.  
  131.  
  132. # from sys import argv
  133. # N = int(argv[1])
  134.  
  135. N = 300
  136.  
  137. Nset = set(range(2, N + 1))
  138. x = find_divisible_by_set(Nset)
  139. assert check_result_set(x, Nset)
  140. print(x)
Success #stdin #stdout 0.03s 9984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9014716836799586623329573573945377845159029877980505339167320652785333649613624539473353602148614605570705738411136004478202144000
https://ideone.com/XMioDX
language:
Python 3 (python  3.12)
created:
10 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!