Solution to Project Euler Problem 50: Consecutive prime sum - The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that adds to a prime below one-hundred. The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953. Which prime, below one-million, can be written as the sum of the most consecutive primes?
Updated: Aug. 10, 2022 — Training Time: 4 minutes
Overseen by: Archangel Macsika
All Training Resources
Scroll for more menu list
Topic: Project Euler Problem 50: Consecutive prime sum.
Difficulty: Advance.
Objective: The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
Input: None.
Expected Output: 997651.
Sikademy Solution in Java Programming Language
package sikademy;
/**
*
* @author Archangel Macsika
* Copyright (c) Sikademy. All rights reserved
*/
public class SikademyEulerSolution {
private static final int LIMIT = pow(10, 6);
public String run() {
boolean[] isPrime = listPrimality(LIMIT);
int[] primes = listPrimes(LIMIT);
long maxSum = 0;
int maxRun = -1;
for (int i = 0; i < primes.length; i++) { // For each index of a starting prime number
int sum = 0;
for (int j = i; j < primes.length; j++) { // For each end index (inclusive)
sum += primes[j];
if (sum > LIMIT)
break;
else if (j - i > maxRun && sum > maxSum && isPrime[sum]) {
maxSum = sum;
maxRun = j - i;
}
}
}
return Long.toString(maxSum);
}
public static boolean[] listPrimality(int n) {
if (n < 0)
throw new IllegalArgumentException("Negative array size");
boolean[] result = new boolean[n + 1];
if (n >= 2)
result[2] = true;
for (int i = 3; i <= n; i += 2)
result[i] = true;
// Sieve of Eratosthenes
for (int i = 3, end = sqrt(n); i <= end; i += 2) {
if (result[i]) {
// Note: i * i does not overflow
for (int j = i * i, inc = i * 2; j <= n; j += inc)
result[j] = false;
}
}
return result;
}
public static int[] listPrimes(int n) {
boolean[] isPrime = listPrimality(n);
int count = 0;
for (boolean b : isPrime) {
if (b)
count++;
}
int[] result = new int[count];
for (int i = 0, j = 0; i < isPrime.length; i++) {
if (isPrime[i]) {
result[j] = i;
j++;
}
}
return result;
}
public static int pow(int x, int y) {
if (x < 0)
throw new IllegalArgumentException("Negative base not supported");
if (y < 0)
throw new IllegalArgumentException("Negative exponent");
int z = 1;
for (int i = 0; i < y; i++) {
if (Integer.MAX_VALUE / z < x)
throw new ArithmeticException("Overflow");
z *= x;
}
return z;
}
public static int sqrt(int x) {
if (x < 0)
throw new IllegalArgumentException("Square root of negative number");
int y = 0;
for (int i = 1 << 15; i != 0; i >>>= 1) {
y |= i;
if (y > 46340 || y * y > x)
y ^= i;
}
return y;
}
public static void main(String[] args) {
SikademyEulerSolution solution = new SikademyEulerSolution();
System.out.println(solution.run());
}
}
Sikademy Solution in Python Programming Language
#
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
#
def compute():
ans = 0
isprime = list_primality(999999)
primes = list_primes(999999)
consecutive = 0
for i in range(len(primes)):
sum = primes[i]
consec = 1
for j in range(i + 1, len(primes)):
sum += primes[j]
consec += 1
if sum >= len(isprime):
break
if isprime[sum] and consec > consecutive:
ans = sum
consecutive = consec
return str(ans)
def sqrt(x):
assert x >= 0
i = 1
while i * i <= x:
i *= 2
y = 0
while i > 0:
if (y + i)**2 <= x:
y += i
i //= 2
return y
def list_primality(n):
result = [True] * (n + 1)
result[0] = result[1] = False
for i in range(sqrt(n) + 1):
if result[i]:
for j in range(i * i, len(result), i):
result[j] = False
return result
def list_primes(n):
return [i for (i, isprime) in enumerate(list_primality(n)) if isprime]
if __name__ == "__main__":
print(compute())