fork download
copy 
  1. # collatz primes
  2.  
  3. from random import randint
  4.  
  5. def isPrime(n, k=5): # miller-rabin
  6.     if n < 2: return False
  7.     for p in [2,3,5,7,11,13,17,19,23,29]:
  8.         if n % p == 0: return n == p
  9.     s, d = 0, n-1
  10.     while d % 2 == 0:
  11.         s, d = s+1, d/2
  12.     for i in range(k):
  13.         x = pow(randint(2, n-1), d, n)
  14.         if x == 1 or x == n-1: continue
  15.         for r in range(1, s):
  16.             x = (x * x) % n
  17.             if x == 1: return False
  18.             if x == n-1: break
  19.         else: return False
  20.     return True
  21.  
  22. primeCount = [0,0,1]
  23.  
  24. def pCount(n):
  25.     k, p = n, 0
  26.     while k > 0:
  27.         if k < n:
  28.             t = p + primeCount[k]
  29.             primeCount.append(t)
  30.             return t
  31.         elif k % 2 == 0:
  32.             k = k / 2
  33.         elif isPrime(k):
  34.             p = p + 1
  35.             k = 3*k + 1
  36.         else:
  37.             k = 3*k + 1
  38.  
  39. n = 3
  40. t = pCount(n)
  41. while t < 65:
  42.     n = n + 1
  43.     t = pCount(n)
  44. print n
  45.  
  46. def collatz(n):
  47.     cs = []
  48.     while n != 1:
  49.         cs.append(n)
  50.         n = 3*n+1 if n&1 else n//2
  51.     cs.append(1)
  52.     return cs
  53.  
  54. filter(isPrime,collatz(1805311))
Time limit exceeded #stdin #stdout 15s 11848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Nauozg
language:
Python (cpython 2.7.16)
created:
8 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!