mersenneforum

VERY BAD ALGORITHM AND CODE!

Apr 20th, 2016
304
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.79 KB | None | 0 0
  1. #!/usr/bin/python
  2.  
  3. from random import randint
  4. from random import randrange
  5.  
  6. mp = 13
  7. tries = 100
  8. startlength = 1
  9. sievesize = 100
  10. k = 5
  11.  
  12. def pp(n, k):
  13.     for p in primes:
  14.         if n < p * p:
  15.             return True
  16.         if n % p == 0:
  17.             return False
  18.     (r, s) = (0, n - 1)
  19.     while s % 2 == 0:
  20.         r += 1
  21.         s //= 2
  22.     for _ in range(k):
  23.         a = randrange(2, n - 1)
  24.         x = pow(a, s, n)
  25.         if x == 1 or x == n - 1:
  26.             continue
  27.         for _ in range(r - 1):
  28.             x = pow(x, 2, n)
  29.             if x == n - 1:
  30.                 break
  31.         else:
  32.             return False
  33.     return True
  34.  
  35. def sieve(n):
  36.     multiples = set()
  37.     for i in range(2, n + 1):
  38.         if i not in multiples:
  39.             yield i
  40.             multiples.update(range(i * i, n + 1, i))
  41.  
  42. if mp > 2 and mp <= 49:
  43.     with open(str(mp)) as f:
  44.         data = f.read()
  45.     primes = list(sieve(sievesize))
  46.     print 'mp:', mp, '  tries:', tries, '  mp length:', len(data), '  start length:', startlength, '  primes in sieve:', len(primes)
  47.     print
  48.     for y in range(int(startlength), len(data)):
  49.         length = int(y)
  50.         flag = False
  51.         counter = 0
  52.         while flag == False:
  53.             counter += 1
  54.             start = randint(0, len(data) - length)
  55.             candidate = int(data[start:start + length])
  56.             if len(str(candidate)) == length:
  57.                 if pp(candidate, k) == True:
  58.                     print
  59.                     print
  60.                     print 'mp:', mp, '  tries:', tries, '  mp length:', len(data), '  result length:', length, '  result:', candidate
  61.                     print
  62.                     flag = True
  63.             if counter == tries:
  64.                 print y,
  65.                 break
  66.     print
Add Comment
Please, Sign In to add comment