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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #10: Summation of primes
  4. Discussions

Project Euler #10: Summation of primes

Problem
Submissions
Leaderboard
Discussions

Sort 190 Discussions, By:

votes

Please Login in order to post a comment

  • SpencerMKSmith
    6 years ago+ 34 comments

    For those that aren't passing test case 6 & 7 it's because your prime checking algorithm isn't efficient enough.

    1. There is a very efficient algorithm called the Sieve of Eratosthenes that is very simple. This alorithm will help you create an array of booleans of size 1000000 that will tell you whether a number is a prime or not. Wikipedia Article

    2. Create another array that holds the sum of all of the prime numbers less than the index (use the array that we created above)

    Once you have the array of sums, simply read the input number, and print sum[inputNumber]. I did this solution in C++ and all test cases finish in < .02 seconds

    Reply if you need any help.

    70|
    Permalink
    View more Comments..
  • prateekmishra95
    5 years ago+ 2 comments
    #!/bin/python3
    
    import sys
    
    limit = 1000000
    suml = [0] * limit
    a = [True] * limit
    a[0] = a[1] = False
    for i, isprime in enumerate(a):
        if isprime:
            suml[i] = suml[i-1] + i
            for n in range(i*i, limit, i):
                a[n] = False
        else:
            suml[i] = suml[i-1]
    
    t = int(input().strip())
    for a0 in range(t):
        n = int(input().strip())
        print(suml[n])
    

    This is python implementation of sieve of eratosthenes with a list that keeps sum of all prime numbers till n, at index n. Passes all test cases.

    7|
    Permalink
  • abhinavkushagra
    5 years ago+ 5 comments

    All I did was :

    1.took help from Project Euler #7
    2.created an extra for loop for finding sum

    That's it :)
    See, how simple it is.

    4|
    Permalink
    View more Comments..
  • seerviashish17
    6 years ago+ 0 comments

    in this problem if test case 1000000 then if your output is 0 than answer is accepted how is possible...there should be answer....37550402023

    4|
    Permalink
  • kapeeshvarma
    3 years ago+ 0 comments

    Create two seperate arrays for primes and sum of primes. Solution in Python 3 :

    import math
    
    t=int(input())
    
    def nprime():
        lim=1000001
        sieve = [True] * lim
        for i in range(3,int(math.sqrt(lim))+1,2):
            if sieve[i]:
                for j in range(i**2,lim,i):
                    sieve[j]=False
        primes=[2]+[i for i in range(3,lim,2) if sieve[i]]
        return primes
    
    def sumprimes(primes):
        out=[]
        sumy=0
        j=0
        for i in range(1000001):
            if primes[j]<=i:
                sumy+=primes[j]
                if j+1<len(primes):
                    j+=1
            out.append(sumy)
        return out
    
    primes=nprime()
    sums=sumprimes(primes)
    for k in range(t):
        n=int(input())
        print(sums[n])
    
    3|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature