Skip to content

Instantly share code, notes, and snippets.

@bgnori
Created January 1, 2017 04:18
Show Gist options
  • Save bgnori/c0d4950a47397194d3ef8d90d4c012db to your computer and use it in GitHub Desktop.
Save bgnori/c0d4950a47397194d3ef8d90d4c012db to your computer and use it in GitHub Desktop.
def isprime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
class Counter:
def __init__(self, n):
self.prepare_prime(n)
self.prepare_sum()
def prepare_prime(self, n):
self.primes = [p for p in range(2, n+1) if isprime(p)]
def prepare_sum(self):
xs = {}
s = 0
for i, p in enumerate(self.primes):
s += p
xs[i] = s
self.sums = xs
def skip(self, nth, rest):
while self.primes[nth] > rest:
nth -= 1
if nth < 0:
return 0
return self.count(nth, rest)
def count(self, nth, rest):
print(nth, self.primes[nth], rest)
if nth == 0:
return rest == self.primes[nth]
if nth < 0:
return 0
if rest < 0:
return 0
if rest == 1:
return 0
if rest == 0:
return 1
return self.count(nth-1, rest) + self.skip(nth, rest - self.primes[nth])
def run(self, x):
return self.count(self.primes.index(x), x)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment