#!/usr/bin/env python # Find the smallest number that can be expressed as # the sum of 3 consecutive prime numbers, # the sum of 9 consecutive prime numbers, # the sum of 27 consecutive prime numbers, # the sum of 31 consecutive prime numbers, # the sum of 1119 consecutive prime numbers, # and is itself a prime number. import gmpy k = 1 seq = [] def add(n): q = 0 global k for _ in xrange(n): k = gmpy.next_prime(k) seq.append(k) def isprime(n): return gmpy.is_prime(n) def plus(site, amount): sum_of_prime = 0 if len(seq) < site + amount: add(site + amount - len(seq)) for prime in seq[site:site + amount]: sum_of_prime += prime return sum_of_prime def isequal(amount, num): site = 0 s = 0 while True: s = plus(site, amount) if s == num: return site elif s > num: return -1 site += 1 block = 0 length = [] while True: ipt = raw_input("amount" + str(block + 1) + ":") if ipt == "": break else: length.append(int(ipt)) block += 1 length.sort(reverse=True) c = True position = [0] * block while c: num = plus(position[0], length[0]) if isprime(num): for i in range(1, block): site = isequal(length[i], num) if site > -1: position[i] = site if i == block - 1: c = False else: position[0] += 1 break else: position[0] += 1 print "\n", "Hunt:", num, "\n" for i in range(block - 1, -1, -1): print "position" + str(length[i]) + ":" + str(position[i])
Monday, November 2, 2009
A simple solution for Google Hunt 2008 warmup
Subscribe to:
Posts (Atom)