/* * Solution to Project Euler problem 87 * Copyright (c) Project Nayuki. All rights reserved. * * https://www.nayuki.io/page/project-euler-solutions * https://github.com/nayuki/Project-Euler-solutions */ import java.util.HashSet; import java.util.Set; public final class p087 implements EulerSolution { public static void main(String[] args) { System.out.println(new p087().run()); } private static final int LIMIT = 50000000; public String run() { int[] primes = Library.listPrimes(Library.sqrt(LIMIT)); Set sums = new HashSet<>(); sums.add(0); for (int i = 2; i <= 4; i++) { Set newsums = new HashSet<>(); for (int p : primes) { long q = 1; for (int j = 0; j < i; j++) q *= p; // q = p^i if (q > LIMIT) break; int r = (int)q; for (int x : sums) { if (x + r <= LIMIT) newsums.add(x + r); } } sums = newsums; } return Integer.toString(sums.size()); } }