We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #50: Consecutive prime sum
  4. Discussions

Project Euler #50: Consecutive prime sum

Sort by

recency

|

31 Discussions

|

  • hamblinglen
     + 2 comments

    python3

    I get everything but test case 9. Curriously, 9 sumtimes returns "Wrong answer" and other times returns "Runtime Error." Has anyone else run into this?

    For some reason hackerrank is failing to post my comment with the code pasted.

  • Someshraj09
     + 0 comments

    I tried in cpp it works and passed all testcases...

    #include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;

ULL sums[1000010] = {0};
ULL MAX = 1000000000000;
ULL N, limit;

char *sieve;

ULL Multiply(ULL a, ULL b, ULL mod)
{
    a %= mod;
    b %= mod;
    
    if(a <= 0xFFFFFFF && b <= 0xFFFFFFF) return (a * b) % mod;
    
    ULL res = 0;    
    
    __asm__
    (
        "mulq %2\n"
        "divq %3"
        : "=&d" (res), "+%a" (a)
        : "rm" (b), "rm" (mod)
        : "cc"
    );
    return res;
}

ULL Power(ULL n, ULL e, ULL mod)
{
    ULL res = 1;
    
    while(e > 0)
    {
        if(e & 1) res = Multiply(res, n, mod);
        
        n = Multiply(n, n, mod);
        e >>= 1;
    }
    return res;
}

bool MillerRabin(ULL n)
{
    const unsigned int mask = 0x208A28Ac; 
    
    vector<int> smallPrimes = {2, 3, 5, 7, 11, 13, 17};
    
    if(n < 31) return (mask & (1 << n)) != 0;
    for(auto p : smallPrimes)
    {
        if(n % p == 0) return 0;
    }
    if(n < 17 * 19) return 1;
    
    const unsigned int STOP = 0;
    const unsigned int A[] = {377687, STOP}, 
                       B[] = {31, 73, STOP},
                       C[] = {2, 7, 61, STOP},
                       D[] = {2, 13, 23, 1662803, STOP},
                       E[] = {2, 3, 5, 7, 11, STOP},
                       F[] = {2, 3, 5, 7, 11, 13, STOP},
                       G[] = {2, 3, 5, 7, 11, 13, 17, STOP},
                       H[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, STOP},
                       I[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, STOP},
                       J[] = {2, 325, 9375, 28178, 450775, 978054, 1795265022, STOP};
    
    const unsigned int *test = J;
    
    if(n < 5329) test = A;
    else if(n < 9080191) test = B;
    else if(n < 4759123141ULL) test = C;
    else if(n < 1122004669633ULL) test = D;
    else if(n < 2152302898747ULL) test = E;
    else if(n < 3474749660383ULL) test = F;
    else if(n < 341550071728321ULL) test = G;
    else if(n < 3825123056546413051ULL) test = H;
    else if(n <= 18446744073709551615ULL) test = I;
    
    auto d = n - 1;
    d >>= 1;
    
    unsigned int shift = 0;
    
    while((d & 1) == 0)
    {
        shift++;
        d >>= 1;
    }
    
    do
    {
        auto x = Power(*test++, d, n);
        
        if(x == 1 || x == n - 1) continue;
        
        bool possible = false;
        
        for(unsigned int r = 0; r < shift; r++)
        {
            x = Multiply(x, x, n);
            
            if(x == 1) return 0;
            if(x == n - 1)
            {
                possible = true;
                break;
            }
        }
        if(!possible) return 0;
    } 
    while(*test != STOP);
                           
    return 1;
}

bool IsPrime(ULL n)
{
    if(n < 2) return 0;
    if(n < 4) return 1;
    if(n % 2 == 0 || n % 3 == 0) return 0;    
    
    return (n >= limit * 2) ? MillerRabin(n) : sieve[n/2];
}

void Sieve(ULL n)
{
    limit = n / 2 + 1;
    sieve = new char[limit];
    fill(sieve, sieve + limit, 1);
    sieve[0] = 0;
    
    for(ULL p = 1; p * p * 2 < limit; p++)
    {
        if(sieve[p])
        {
            for(ULL i = p * 3 + 1; i < limit; i += (p * 2 + 1))
            {
                sieve[i] = 0;
            }
        }
    }
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    vector<long long> queries(t);
    long long mx = 0;
    
    for(int i=0; i<t; i++)
    {
        cin >> queries[i];
        mx = max(mx, queries[i]);
    }    
    Sieve(10000000);        
    
    sums[1] = 2;         
    ULL p = 3;    
    
    int size = 1;
    int maxLength = 0;
    int min_r[33] = {0};
    
    vector<pair<ULL, ULL>> results;        
    
    for(ULL p = 3; p <= mx; p += 2)
    {
        if(sums[size] + p > mx) break;
        
        if(IsPrime(p))
        {
            size++;
            sums[size] = sums[size - 1] + p;
                    
            for(int i = 0; i <= 32 && i + maxLength + 1 <= size; i++)
            {                        
                for(int j = max(i + maxLength + 1, min_r[i]); j <= size; j++)
                {
                    ULL sum = sums[j] - sums[i];
                    
                    if(sum > mx) break;
                    
                    min_r[i] = j + 1;
                    
                    if(IsPrime(sum))
                    {
                        results.push_back({sum, (j - i)});
                        maxLength = j - i;
                        goto next;
                    }
                }
            }
        }
        next:
        continue;
    }  
    
    for(auto n : queries)
    {
        pair<ULL, ULL> prev;
        
        for(auto it : results)
        {
            if(it.first > n) break;
            
            prev = it;
        }
        cout << prev.first << " " << prev.second << "\n";
    }
    return 0;
}

  • Someshraj09
     + 0 comments

    This is my python solution for this question but only 5 testcases will be passed......

    import math

prs = []
prSum = []

def mulmod(a, b, mdlo):
    if a <= 0xFFFFFFF and b <= 0xFFFFFFF:
        return (a * b) % mdlo
    result = 0
    factor = a % mdlo
    while b > 0:
        if b & 1:
            result += factor
            if result >= mdlo:
                result %= mdlo
        factor <<= 1
        if factor >= mdlo:
            factor %= mdlo
        b >>= 1
    return result

def powmod(base, expo, mdlo):
    result = 1
    while expo > 0:
        if expo & 1:
            result = mulmod(result, base, mdlo)
        base = mulmod(base, base, mdlo)
        expo >>= 1
    return result

def isPrime(p):
    biPri = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) | (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19) | (1 << 23) | (1 << 29)
    if p < 31:
        return (biPri & (1 << p)) != 0
    if p % 2 == 0 or p % 3 == 0 or p % 5 == 0 or p % 7 == 0 or p % 11 == 0 or p % 13 == 0 or p % 17 == 0:
        return False
    if p < 17 * 19:
        return True
    tesAg1 = [377687, 0]
    tesAg2 = [31, 73, 0]
    tesAg3 = [2, 7, 61, 0]
    tesAg4 = [2, 13, 23, 1662803, 0]
    tesAg7 = [2, 325, 9375, 28178, 450775, 9780504, 1795265022, 0]
    tesAgst = tesAg7
    
    if p < 5329:
        tesAgst = tesAg1
    elif p < 9080191:
        tesAgst = tesAg2
    elif p < 4759123141:
        tesAgst = tesAg3
    elif p < 1122004669633:
        tesAgst = tesAg4

    d = p - 1
    d >>= 1
    shift = 0
    while (d & 1) == 0:
        shift += 1
        d >>= 1
    while tesAgst[0] != 0:
        x = powmod(tesAgst[0], d, p)
        if x == 1 or x == (p - 1):
            tesAgst = tesAgst[1:]
            continue
        mPrime = False
        for r in range(shift):
            x = powmod(x, 2, p)
            if x == 1:
                return False
            if x == (p - 1):
                mPrime = True
                break
        if not mPrime:
            return False
        tesAgst = tesAgst[1:]
    return True

def morePrimes(num):
    global prs, prSum
    if not prs:
        prs = [2, 3]
        prSum = [2]
    for i in range(prs[-1] + 2, num + 1, 2):
        isPrime = True
        for x in prs:
            if x * x > i:
                break
            if i % x == 0:
                isPrime = False
                break
        if isPrime:
            prs.append(i)
    for i in range(len(prSum), len(prs)):
        prSum.append(prSum[-1] + prs[i])

if __name__ == "__main__":
    ppb = int(math.pow(10, 4))
    morePrimes(ppb)
    T = int(input())
    while T > 0:
        N = int(math.pow(10, 6))
        N = int(input())
        best = 2
        maxLength = 0
        start = 0
        while prs[start] <= 131 and prs[start] <= N:
            subtract = 0
            if start > 0:
                subtract = prSum[start - 1]
            pos = start + maxLength
            while prSum[pos] - subtract <= N:
                pos += 1
                if pos + 100 >= len(prs):
                    morePrimes(len(prs) + ppb)
            pos -= 1
            while (pos - start) > maxLength:
                sum = prSum[pos] - subtract
                if isPrime(sum):
                    maxLength = pos - start
                    best = sum
                    break
                pos -= 1
            start += 1
        if best >= 2:
            maxLength += 1
        print(best, maxLength)
        T -= 1

  • ibnahmadmohamed8
     + 0 comments

    java code

    import java.util.Scanner;

    public class Solution {

    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int T = scanner.nextInt();

    for (int t = 0; t < T; t++) {
        long N = scanner.nextLong();

        findLongestConsecutivePrimeSum(N);
    }

    scanner.close();
}

private static void findLongestConsecutivePrimeSum(long N) {
    boolean[] isPrime = sieveOfEratosthenes(N);
    long resultPrime = 0;
    int maxLength = 0;

    for (int start = 2; start < N; start++) {
        long sum = 0;
        int length = 0;

        for (int current = start; current < N; current++) {
            if (isPrime[current]) {
                sum += current;
                length++;

                if (sum > N) {
                    break;
                }

                if (isPrime[(int) sum] && length > maxLength) {
                    maxLength = length;
                    resultPrime = sum;
                }
            }
        }
    }

    System.out.println(resultPrime + " " + maxLength);
}

private static boolean[] sieveOfEratosthenes(long limit) {
    boolean[] isPrime = new boolean[(int) (limit + 1)];
    for (int i = 2; i <= limit; i++) {
        isPrime[i] = true;
    }

    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime;
}

    }

  • nc1969
     + 0 comments

    Hmmm... Test case 9 failed, the answer is wrong. What is this? BTW what is the correct answer for 2: 2 1? @shashank21j

    Update: Never mind, I've found out the issue, I had a bug in my binary search implementaion.