diff options
| author | Iru Cai <mytbk920423@gmail.com> | 2018-05-25 14:13:16 +0800 |
|---|---|---|
| committer | Iru Cai <mytbk920423@gmail.com> | 2018-05-25 14:13:16 +0800 |
| commit | d5c645bf83f144838e84b21e4941a0e42b0a9a61 (patch) | |
| tree | 7164988f5dcfa2264d50f4c184f4c278f5983d27 /euler50.myr | |
| parent | 3caa8876e4c1d71cf8973d0d78231f16a0cd5b93 (diff) | |
| download | project_euler-d5c645bf83f144838e84b21e4941a0e42b0a9a61.tar.xz | |
47, 49, 50
Diffstat (limited to 'euler50.myr')
| -rw-r--r-- | euler50.myr | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/euler50.myr b/euler50.myr new file mode 100644 index 0000000..4fd1b07 --- /dev/null +++ b/euler50.myr @@ -0,0 +1,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) +} + |