CODEWITHSUNDEEP
python
chunk
chunk

Reputation: 37

Problem with finding prime numbers in range

Program description:

Program accepts a segment of N numbers, [1024, 289213] in my case. Then it should output a summ of all prime numbers within this segment.

My solution:

for i in range(1024, 289213):
    isPrime = True
    for j in range(2, i // 2):
        if (i % j) == 0:
            isPrime = False
            break
    if isPrime:
        n += i
print(n)

Problem: The program works perfectly with small segments, like [3,17], however in case of [1024, 289213] it takes forever to load.

What could be the source of the problem? Maybe there's even a better way to code this? Thank you in advance.

Upvotes: 0

Views: 66

Answers (1)

Sharvin
Sharvin

Reputation: 98

This set of codes will solve the problem you are facing:

from math import sqrt 

# Function to compute the prime number 
# Time Complexity is O(sqrt(N)) 
def checkPrime(numberToCheck) : 

    if numberToCheck == 1 : 
        return False

    for i in range(2, int(sqrt(numberToCheck)) + 1) : 

        if numberToCheck % i == 0 : 
            return False

    return True

def primeSum(l, r) : 

    sum = 0

    for i in range(r, (l - 1), -1) : 

        # Check for prime 
        isPrime = checkPrime(i) 
        
        if (isPrime) : 

            # Sum the prime number 
            sum += i 

    return sum

# Time Complexity is O(r x sqrt(N)) 
 
if __name__ == "__main__" : 

    l, r = 1024, 289213

    # Call the function with l and r 
    print(primeSum(l, r))

Output:

3463762527

Please note that it will take a few seconds to get the output.

Upvotes: 1

Related Questions