blob: 4fd1b07b4d24bffb513d76b48324b27a4741ed58 (
plain)
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
use std
var primes: int[100000]
var nprimes: int
const sieve = {
nprimes = 1
primes[0] = 2
for var i = 3; i < 1_000_000; i++
for var j = 0; j < nprimes; j++
if i % primes[j] == 0
break
;;
if primes[j] * primes[j] > i
primes[nprimes] = i
nprimes++
break
;;
;;
;;
}
const isprime = {n
for var i = 0; i < nprimes; i++
if n % primes[i] == 0
-> false
;;
if (primes[i]*primes[i] > n)
-> true
;;
;;
-> false
}
const prime_terms = {n, limit
var L = n / limit
var i = 0
var j = 0
var sum = 0
while primes[i] < L
/* calculate a[i..j] */
while sum < n
sum += primes[j]
if sum == n
-> j - i + 1
;;
j++
;;
/* calculate a[i..j-1] */
while sum > n
sum -= primes[i]
i++
if sum == n
-> j - i
;;
;;
;;
-> 0
}
const main = {
sieve()
std.put("{} primes below 1000000\n", nprimes)
var maxL = 21
var ans = 953
for var i = 954; i < 1_000_000; i++
if !isprime(i)
continue
;;
var pt = prime_terms(i, maxL)
if pt > maxL
maxL = pt
ans = i
;;
;;
std.put("len = {} ans = {}\n", maxL, ans)
}
|