Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/python
- from random import randint
- from random import randrange
- mp = 13
- tries = 100
- startlength = 1
- sievesize = 100
- k = 5
- def pp(n, k):
- for p in primes:
- if n < p * p:
- return True
- if n % p == 0:
- return False
- (r, s) = (0, n - 1)
- while s % 2 == 0:
- r += 1
- s //= 2
- for _ in range(k):
- a = randrange(2, n - 1)
- x = pow(a, s, n)
- if x == 1 or x == n - 1:
- continue
- for _ in range(r - 1):
- x = pow(x, 2, n)
- if x == n - 1:
- break
- else:
- return False
- return True
- def sieve(n):
- multiples = set()
- for i in range(2, n + 1):
- if i not in multiples:
- yield i
- multiples.update(range(i * i, n + 1, i))
- if mp > 2 and mp <= 49:
- with open(str(mp)) as f:
- data = f.read()
- primes = list(sieve(sievesize))
- print 'mp:', mp, ' tries:', tries, ' mp length:', len(data), ' start length:', startlength, ' primes in sieve:', len(primes)
- print
- for y in range(int(startlength), len(data)):
- length = int(y)
- flag = False
- counter = 0
- while flag == False:
- counter += 1
- start = randint(0, len(data) - length)
- candidate = int(data[start:start + length])
- if len(str(candidate)) == length:
- if pp(candidate, k) == True:
- print
- print
- print 'mp:', mp, ' tries:', tries, ' mp length:', len(data), ' result length:', length, ' result:', candidate
- print
- flag = True
- if counter == tries:
- print y,
- break
- print
Add Comment
Please, Sign In to add comment