Sum of all prime numbers between 1 and N in Python

Question

I'm new to programming. While trying to solve this problem, I'm getting the wrong answer. I checked my code a number of times but was not able to figure out the mistake. Please, help me on this simple problem. The problem is as follows:

Given a positive integer N, calculate the sum of all prime numbers between 1 and N (inclusive). The first line of input contains an integer T denoting the number of test cases. T testcases follow. Each testcase contains one line of input containing N. For each testcase, in a new line, print the sum of all prime numbers between 1 and N.

And my code is:

from math import sqrt 
sum = 0
test = int(input())
for i in range(test):
    max = int(input())
    if max==1:
        sum = 0
    elif max==2:
        sum += 2
    else:    
        sum = sum + 2
        for x in range(3,max+1):
            half = int(sqrt(max)) + 1
            for y in range(2,half):
                res = x%y
                if res==0:
                    sum = sum + x
                    break
    print(sum)     

For input 5 and 10, my code is giving output 6 and 48 respectively, while the correct answer is 10 and 17 respectively. Please, figure out the mistake in my code.

Answer 1

Here, I implemented simple program to find the sum of all prime numbers between 1 to n. Consider primeAddition() as a function and ip as an input parameter. It may help you to solve your problem.Try it.

Code snippet:

def primeAddition(ip): 
    # list to store prime numbers...
    prime = [True] * (ip + 1) 

    p = 2
    while p * p <= ip: 
        # If prime[p] is not changed, then it is a prime...
        if prime[p] == True: 
            # Update all multiples of p...
            i = p * 2
            while i <= ip: 
                prime[i] = False
                i += p 
        p += 1    

    # Return sum of prime numbers...
    sum = 0
    for i in range (2, ip + 1): 
        if(prime[i]): 
            sum += i 
    return sum

#The program is ready... Now, time to call the primeAddition() function with any argument... Here I pass 5 as an argument...
#Function call...

print primeAddition(5)

Answer 2

First of all, declare sum to be zero at the beginning of the for i loop.

The problem lies in the if statement at almost the very end of the code, as you add x to the sum, if the res is equal to zero, meaning that the number is indeed not a prime number. You can see that this is the case, because you get an output of 6 when entering 5, as the only non-prime number in the range 1 to and including 5 is 4 and you add 2 to the sum at the beginning already.

Last but not least, you should change the

half = int(sqrt(max)) + 1

line to

half = int(sqrt(x)) + 1

Try to work with my information provided and fix the code yourself. You learn the most by not copying other people's code.

Happy coding!

Answer 3

Because your logic is not correct.

for y in range(2,half):
    res = x%y
    if res==0:
        sum = sum + x
        break

here you check for the factors and if there is a factor then adds to sum which is opposite of the Primes. So check for the numbers where there is no factors(except 1).

from math import sqrt 

test = int(input())
for i in range(test):
    sum = 0
    max = int(input())
    if max==1:
        sum = 0
    elif max==2:
        sum += 2
    else:    
        sum = sum + 2
        for x in range(3,max+1):
            half = int(sqrt(x)) + 1
            if all(x%y!=0 for y in range(2,half)):
                sum = sum + x
   print(sum)     

Answer 4

A slight modification to what you have:

from math import sqrt 
sum = 0
test = int(input())
max = int(input())


for x in range(test,max+1):
    if x == 1:
        pass
    else:
        half = int(sqrt(x)) + 1
        for y in range(2,half):
            res = x%y
            if res==0:
                break
        else:
            sum = sum + x

print(sum)    

Your biggest error was that you were doing the sum = sum + x before the break rather than outside in an else statement.

PS: (although you can) I'd recommend not using variable names like max and sum in your code. These are special functions that are now overridden.

Answer 5

This is the most broken part of your code, it's doing the opposite of what you want:

res = x%y
if res==0:
    sum = sum + x
    break

You only increment sum if you get through the entire loop without breaking. (And don't use sum as you're redefining a Python built-in.) This can be checked using the special case of else on a for loop, aka "no break". I've made that change below as well as corrected some inefficiencies:

from math import sqrt

T = int(input())

for _ in range(T):
    N = int(input())

    sum_of_primes = 0

    if N < 2:
        pass
    elif N == 2:
        sum_of_primes = 2
    else:
        sum_of_primes = 2

        for number in range(3, N + 1, 2):

            for odd in range(3, int(sqrt(number)) + 1, 2):
                if (number % odd) == 0:
                    break
            else:  # no break
                sum_of_primes += number

    print(sum_of_primes)

OUTPUT

> python3 test.py
3
5
10
10
17
23
100
>

Answer 6

I believe the mistake in your code might be coming from the following lines of code:

for x in range(3,max+1):
        half = int(sqrt(max)) + 1

Since you are looping using x, you should change int(sqrt(max)) to int(sqrt(x)) like this:

for x in range(3,max+1):
        half = int(sqrt(x)) + 1

Your code is trying to see if max is prime N times, where you should be seeing if every number from 1-N is prime instead.

This is my first time answering a question so if you need more help just let me know.