Skip to content

Instantly share code, notes, and snippets.

@lykkin
Created February 13, 2015 18:30
Show Gist options
  • Save lykkin/85154d0fb799ce9b9ee6 to your computer and use it in GitHub Desktop.
Save lykkin/85154d0fb799ce9b9ee6 to your computer and use it in GitHub Desktop.
from functools import wraps
from datetime import datetime
def time(f):
@wraps(f)
def inner(*args, **kwargs):
start = datetime.now()
res = f(*args, **kwargs)
delta = datetime.now() - start
print delta
return res
return inner
def memo(f):
cache = {}
@wraps(f)
def inner(*args, **kwargs):
key = str(args) + str(kwargs)
try:
return cache[key]
except KeyError:
cache[key] = f(*args, **kwargs)
return cache[key]
return inner
def sieve(n):
li = [2] + range(3, n, 2)
cur = li.pop(0)
res = []
while(cur < n**.5):
li = [x for x in li if x % cur != 0]
res += [cur]
cur = li.pop(0)
return res + [cur] + li
def millar(n):
if n == 2:
return True
d = n - 1
s = 0
while d % 2 == 0:
s += 1
d /= 2
def check(a, s, d, n):
c = a**d % n
r = 0
if c == 1:
return True
while r < s:
if c == n - 1:
return True
c = c**2 % n
r += 1
return False
return reduce(lambda x, y: x and y,
map(lambda x: check(x, s, d, n),
range(2, min(n, 4))
)
)
def millarlist(n):
return filter(lambda x: millar(x), range(2, n))
def est(n):
print len(millarlist(n)) - len(sieve(n))
print len(sieve(999999999))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment