Prime Summations

#include <iostream>
#include <vector>

int prime_summations() {
    const int N = 1000;
    std::vector<bool> is_prime(N + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (long long i = 2; i <= N; ++i) {
        if (is_prime[i]) {
            for (long long j = i * i; j <= N; j += i) {
                is_prime[j] = false;
            }
        }
    }
    std::vector<int> primes;
    for (int i = 2; i <= N; ++i) {
        if (is_prime[i]) primes.push_back(i);
    }
    std::vector<long long> ways(N + 1, 0);
    ways[0] = 1;
    for (int p : primes) {
        for (int j = p; j <= N; ++j) {
            ways[j] += ways[j - p];
        }
    }
    for (int n = 2; n <= N; ++n) {
        if (ways[n] > 5000) return n;
    }
    return -1;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << prime_summations() << std::endl;
}
#endif

package main

import "fmt"

func primeSummations() int {
    limit := 1000
    isPrime := make([]bool, limit+1)
    for i := range isPrime {
        isPrime[i] = true
    }
    isPrime[0], isPrime[1] = false, false
    for i := 2; i*i <= limit; i++ {
        if isPrime[i] {
            for j := i * i; j <= limit; j += i {
                isPrime[j] = false
            }
        }
    }
    primes := []int{}
    for i := 2; i <= limit; i++ {
        if isPrime[i] {
            primes = append(primes, i)
        }
    }
    n := 2
    for {
        ways := 0
        dp := make([]int, n+1)
        dp[0] = 1
        for _, p := range primes {
            if p > n {
                break
            }
            for j := p; j <= n; j++ {
                dp[j] += dp[j-p]
            }
        }
        ways = dp[n]
        if ways > 5000 {
            return n
        }
        n++
    }
}

func main() {
    fmt.Println(primeSummations())
}

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;

public class Solution077 implements Solution {
  public String solve() {
    final int N = 1000;
    boolean[] is_prime = new boolean[N + 1];
    for (int i = 0; i <= N; ++i) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for (long i = 2; i <= N; ++i) {
      if (is_prime[(int)i]) {
        for (long j = i * i; j <= N; j += i) {
          is_prime[(int)j] = false;
        }
      }
    }
    int[] primes = new int[N];
    int count = 0;
    for (int i = 2; i <= N; ++i) {
      if (is_prime[i]) primes[count++] = i;
    }
    long[] ways = new long[N + 1];
    ways[0] = 1;
    for (int i = 0; i < count; ++i) {
      int p = primes[i];
      for (int j = p; j <= N; ++j) {
        ways[j] += ways[j - p];
      }
    }
    for (int n = 2; n <= N; ++n) {
      if (ways[n] > 5000) return String.valueOf(n);
    }
    return "-1";
  }
}

function primeSummations() {
  const N = 1000;
  const isPrime = new Array(N + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i <= N; ++i) {
    if (isPrime[i]) {
      for (let j = i * i; j <= N; j += i) {
        isPrime[j] = false;
      }
    }
  }
  const primes = [];
  for (let i = 2; i <= N; ++i) {
    if (isPrime[i]) primes.push(i);
  }
  const ways = new Array(N + 1).fill(0n);
  ways[0] = 1n;
  for (let p of primes) {
    for (let j = p; j <= N; ++j) {
      ways[j] += ways[j - p];
    }
  }
  for (let n = 2; n <= N; ++n) {
    if (ways[n] > 5000n) return n;
  }
  return -1;
}

module.exports = {
  answer: () => primeSummations()
};

def solve():
    import math
    def sieve(n):
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(math.sqrt(n)) + 1):
            if is_prime[i]:
                for j in range(i*i, n+1, i):
                    is_prime[j] = False
        return [i for i in range(2, n+1) if is_prime[i]]
    limit = 1000
    primes = sieve(limit)
    dp = [0] * (limit + 1)
    dp[0] = 1
    for p in primes:
        for j in range(p, limit + 1):
            dp[j] += dp[j - p]
    for n in range(2, limit + 1):
        if dp[n] > 5000:
            return n

if __name__ == "__main__":
    print(solve())

pub fn prime_summations() -> u64 {
    const LIMIT: usize = 1000;
    let primes = sieve(LIMIT);
    let mut ways = vec![0u32; LIMIT + 1];
    ways[0] = 1;
    for &p in &primes {
        for j in p..=LIMIT {
            ways[j] += ways[j - p];
        }
    }
    for n in 2..=LIMIT {
        if ways[n] > 5000 {
            return n as u64;
        }
    }
    0
}

fn sieve(limit: usize) -> Vec<usize> {
    let mut is_prime = vec![true; limit + 1];
    is_prime[0] = false;
    if limit > 0 {
        is_prime[1] = false;
    }
    for i in 2..=((limit as f64).sqrt() as usize) {
        if is_prime[i] {
            for j in ((i * i)..=limit).step_by(i) {
                is_prime[j] = false;
            }
        }
    }
    (2..=limit).filter(|&x| is_prime[x]).collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn euler_077() {
        assert_eq!(prime_summations(), 71);
    }
}