fork download
copy 
  1. # nearly square divisors, revisited
  2.  
  3. def factors(n): # 2,3,5-wheel
  4.     ws = [1,2,2,4,2,4,2,4,6,2,6]
  5.     w, f, fs = 0, 2, []
  6.     while f*f <= n:
  7.         while n % f == 0:
  8.             fs.append(f)
  9.             n /= f
  10.         f, w = f + ws[w], w+1
  11.         if w == 11: w = 3
  12.     if n < f*f: fs.append(n)
  13.     return fs
  14.  
  15. def knap(target, xs):
  16.     if xs == []: return 0
  17.     if target < xs[0]:
  18.         return knap(target, xs[1:])
  19.     else:
  20.         return max(xs[0] + knap(target-xs[0],xs[1:]), \
  21.                    knap(target, xs[1:]))
  22.  
  23. def nsd(n):
  24.     from math import log, exp
  25.     fs = map(log, factors(n)[::-1])
  26.     b = int(round(exp(knap(sum(fs)/2, fs))))
  27.     return n/b, b
  28.  
  29. print nsd(224403121196654400)
Success #stdin #stdout 1.17s 9024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(473753280L, 473670855)
https://ideone.com/n5Wcja
language:
Python (cpython 2.7.16)
created:
7 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!