Euler Projesi 249. Soru

Asal Altküme Toplamları

5000'den küçük asal sayıların kümesi S={2,3,5,...,4999} olsun.

Elemanları toplamı bir asal sayı olan S'nin altkümeleri sayısı kaçtır?
Cevap olarak sadece en sağ 16 rakamı giriniz.

[Project Euler]

Cevap: 9275262564250418

ML let sieve m = let rec loop_i arr m i = let rec loop_j arr m i j = if j >= m then arr else (arr.(j) <- 0; loop_j arr m i (i+j)) in if i * i >= m then arr else loop_i (loop_j arr m i (i*i)) m (i+1) in let arr = loop_i (Array.init m (fun i -> if i < 2 then 0 else 1)) m 2 in fun k -> arr.(k) = 1 let ( ++ ), ( -- ) = Int64.add, Int64.sub let add10 a b = let t = a ++ b in if t < 10000000000000000L then t else t -- 10000000000000000L let main n = let isprime = sieve 1600000 in let rec collect acc n = if n = 1 then acc else collect (if isprime n then n :: acc else acc) (n-1) in let foldfunc (arr, max) n = let rec loop arr v i = if i < 0 then arr else (arr.(v+i) <- add10 arr.(v+i) arr.(i); loop arr v (i-1)) in loop arr n max, n + max in let rec sum arr acc i = if i = 0 then acc else sum arr (if isprime i then add10 acc arr.(i) else acc) (i-1) in let arr = Array.init 1548137 (fun i -> if i = 0 then 1L else 0L) in let (arr, max) = List.fold_left foldfunc (arr, 0) (collect [] 5000) in sum arr 0L max let _ = Printf.printf "Answer: %Ld\n" (main ()) C,C++: #include <stdio.h> #include <memory.h> #define SIZE 1570000 typedef unsigned __int64 U64; static char primes[SIZE]; static U64 buf[SIZE]; static U64 l16 = 10000000000000000ULL; void sieve() { memset(primes, 1, sizeof primes); primes[0] = primes[1] = 0; for (int i = 2; i * i < SIZE; i++) { for (int j = i * i; j < SIZE; j += i) primes[j] = 0; } } int main(int argc, char **argv) { sieve(); for (int i = 0; i < SIZE; i++) buf[i] = 0; buf[0] = 1; int max = 0; for (int i = 2; i < 5000; i++) { if (primes[i]) { for (int j = max; j >= 0; j--) { buf[j + i] += buf[j]; if (buf[j+i] >= l16) buf[j+i] -= l16; } max += i; } } U64 sum = 0; for (int i = 2; i <= max; i++) if (primes[i]) sum = (sum + buf[i]) % l16; printf("%I64d\n", sum); return 0L; } PYTHON: from collections import defaultdict def p249(limit = 5000): ss = defaultdict(int) ss[0] = 1 # empty set for p in primes.upto(limit): for s in sorted(ss.keys(), reverse=True): ss[s+p] += ss[s] return sum(ss[s] for s in ss if is_prime(s))