I am trying to write some code for project euler problem 10, in which you are required to find the sum of all the prime numbers less than 2 million. Now the code is taking too long to execute. I would like to know how can I improve my code as it did work for prime numbers less than 100.

# =================== isPrime Algorithm ====================
# I created this program to check whether a number is prime or not

def isPrime(n):
    # Prime number algorithm
    if n == 2:
        return True
    elif n == 3:
        return True
    else:
        for x in range(3, n, 2):
            if n % x == 0:
                return False
            else:
                continue
    return True

def main():
    # Collects the prime numbers between 1 and 100
    prime_arr = [] # I used this array just to test I could have easily printed the num in the for loop below

    for num in range(1, 101, 2):
        if isPrime(num) == True:
            prime_arr.append(num)
        else:
            continue

    print(prime_arr)

# Call the main function
main()

Recommended Answers

All 5 Replies

Thanks alot I will look at it

The traditional (and mathematically rigorous) method to determine primes is using the Sieve of Aristostenes. Your method will work for small primes, but breaks down quickly, or becomes computationally overwhelmed by the number of itererations required. This Wikipedia article explaines it pretty well: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

import re 
def is_prime(num): return not re.match(r"^1?$|^(11+?)\1+$", "1" * num)
def pri(num): return is_prime(num)
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.