-
Notifications
You must be signed in to change notification settings - Fork 1
/
050.boo
36 lines (30 loc) · 970 Bytes
/
050.boo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
We use a list of primes (generated by sieve). We call it "cache".
We cache the sum of primes upto index "i" in "cache". We call it T[i].
T[j]-T[i] means "the sum of all consecutive primes in the index interval (j,i]"
And, for each pair (i,j) in T, we see if the results in a prime.
Eg.
i,j = (0, 6)
E[6] - E[0] = 41, the sum of primes from indices 1 to 6
41 is prime, so 41 is a prime that is composed by the sum of 6 (j-1) primes
*/
import System
import System.Linq.Enumerable
import System.Collections.Generic
primes = PrimeNumbers(10**6)
cache = primes.Cache.ToArray()
T = array(long, cache.Length+1)
T[0] = 0
for i in range(1,cache.Length+1):
T[i] = T[i-1] + cache[i-1]
max = 0
for i in range(T.Length):
if i+max >= T.Length: continue
for j in range(i+max, T.Length):
k = T[j] - T[i]
if k>=10**6: break
if primes.IsPrime(k) and j-i > max:
max = j-i
answer = k
print answer
assert answer == 997651