0
sum_ans=17
for i in range(11,2000000):
    for j in range(2,int(i**0.5)):
        if i%j==0:
            break
    else:
        sum_ans+=i
print(sum_ans)

The code i have return gives answer 143064094781 and the correct answer is 142913828922 but i can not figure out where i have gone wrong. So can any one help me.

Kishan
  • 1
  • 1
  • 1
  • 3
    I think i**0.5 + 1 should do the job, because the second argument of range() is exclusive. – Creepsy Aug 02 '20 at 12:18
  • Your `17` includes 2, which is the only even prime. That means you only need to try `i` odd: 11, 13, 15, ... because all the even numbers > 11 are composite. Given that `i` is odd, there is no need to test `j` == 2; start at 3 and again only work with odd values: 3, 5, 7, 9, ... – rossum Aug 02 '20 at 16:48

4 Answers4

1

Range's stop parameter is exclusive. This means that your code is only calculating j from 2 to 1 less than i**0.5. To fix this you can add 1, meaning that your end code will look a little like this, providing the correct output of 142913828922:

sum_ans=17
for i in range(11,2000000):
    for j in range(2,int(i**0.5+1)):
        if i%j==0:
            break
    else:
        sum_ans+=i
print(sum_ans)
Minion3665
  • 879
  • 11
  • 25
  • Why raise i to the .5? What is i**0.5? – BrianBeing Feb 05 '22 at 19:14
  • @BrianBeing a number to the power of 0.5 is the same as saying the square root of that number; when looking at primes [you only need to check up to the square root of the number](https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr) to see if it's prime – Minion3665 Feb 06 '22 at 00:28
  • 1
    Good answer. It suggests that the difference between the correct sum and OP's sum equals the sum of the numbers of the form `p^2` which are below 2 million. – John Coleman Oct 28 '22 at 00:35
0

What about about this:

def isPrime(x):
    prime = True
    for i in range(2, x):
        if x % i == 0:
            prime = False
            break
        else:
            continue
    return prime

primes = (a for a in range(2, 2000000) if isPrime(a))
print(sum(primes))

# output
142913828922

This code will take a few minutes to execute. Buckle up!!

Zy Taga
  • 89
  • 6
0

def sumPrimes(n):
    sum =0
    for i in range(2 ,n):
        for j in range(2, int(i / 2) +1):
            if (i % j) == 0:
                break
        else:
            sum += i
    return sum

print(sumPrimes(2000000))
bero
  • 21
  • 6
  • 1
    This is extremely inefficient. Going all the way up to `i/2` to certify a number as prime becomes prohibitively expensive once `i` gets large. For example, to certify that `1000003` is prime, your code performs 500,000 remainder operations. If you used OP's idea of going to the square root and improved it only testing if the odd numbers in that range are factors, you could get by with just 500 operations. For prime numbers above 1 million, your code is working 1,000 times harder than it needs to. I have been running your code for over 10 minutes, and it still hasn't stopped. – John Coleman Oct 28 '22 at 00:52
0

If you iterating over all numbers below 2 million, you might as well sieve them using the Sieve of Eratoshenes:

from math import ceil, sqrt

def sieve(n):
    nums = list(range(2,n+1))
    primes = []
    p = 2
    k = 1+ ceil(sqrt(n))
    while p < k:
        primes.append(p)
        nums = [num for num in nums[1:] if num % p > 0]
        p = nums[0]
    return primes + nums

Then sum(sieve(2000000)) evaluates to 142913828922. It takes about 5 seconds to run on my machine.

John Coleman
  • 51,337
  • 7
  • 54
  • 119