fork download
copy 
  1. from random import randrange
  2.  
  3. _small_primes = set((2, 3, 5, 7, 11, 13, 17, 19, 23))
  4.  
  5. def is_prime(n, k=25):
  6.     n = abs(n)
  7.     if n in _small_primes:
  8.         return True
  9.     for pi in _small_primes:
  10.         if not n % pi:
  11.             return False
  12.     if pow(2, n-1, n) != 1:
  13.         return False
  14.     d, s = n - 1, 0
  15.     while not d % 2:
  16.         d //= 2
  17.         s += 1
  18.  
  19.     def is_spsp(n, a):
  20.         t = pow(a, d, n)
  21.         if t == 1:
  22.             return True
  23.         for _ in range(s):
  24.             if t == n - 1:
  25.                 return True
  26.             t = (t * t) % n
  27.         return False
  28.     return all(is_spsp(n, randrange(2, n-1)) for _ in range(k))
  29.  
  30.  
  31. def kalai(n):
  32.     while True:
  33.         s, r, si = n, 1, []
  34.         while s > 1:
  35.             s = randrange(1, s+1)
  36.             if is_prime(s):
  37.                 r *= s
  38.                 si.append(s)
  39.         if r <= n and randrange(1, n+1) <= r:
  40.             return r, list(reversed(si))
  41.  
  42. print(kalai(10**30))
Success #stdin #stdout 0.11s 12000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(406726036134521702413541748596, [2, 2, 17, 19, 67, 929, 182887, 27654518919777443])
https://ideone.com/wPKIYA
language:
Python 3 nbc (python 3.7.3)
created:
6 years ago
visibility:
secret

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!