Calculating Primes and Appending to a List

Question

I've recently started attempting to solve problems on project Euler using python, and have hit this road bump when trying to calculate primes and append them to a list. I have written the following code, but I'm confused as to why it doesn't output anything when I run it.

import math

primes = []

def isPrime(i):
    if number<=1:
        return False
    if number==2:
        return True
    if number%2==0:
        return False
    for i in range(3,int(sqrt(number))+1):
        if number%i==0:
            return False
    return True

for i in range (1, 9999999):
    if isPrime(i) == True:
        primes.append(i)
    else:
        continue
print(primes)

Answer 1

Try :

import math

primes = []

def isPrime(number):
    if number<=1:
        return False
    if number==2:
        return True
    if number%2==0:
        return False
    for i in range(3,int(math.sqrt(number))+1):
        if number%i==0:
            return False
    return True

for i in range (1, 9999999):
    if isPrime(i) == True:
        primes.append(i)

print(primes)

Answer 2

Try this:

import math

primes = []

def isPrime(number):
    if number<=1:
        return False
    if number==2:
        return True
    if number%2==0:
        return False
    for ind in range(3,int(math.sqrt(number))+1):
        if number%ind==0:
            return False
    return True

for i in range (1, 100):
    if isPrime(i) == True:
        primes.append(i)
    else:
        continue

print(primes)

To show it working, I print the first 100:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Answer 3

If you're building up a list of primes, it can be more efficient to use that list as part of your solution.

For example, this loop:

for i in range(3, int(math.sqrt(number)) + 1):

For the prime 1009 will test ~30 numbers but there are only 10 primes less than the square root of 1009 that actually need to be tested. And this difference just keeps increasing.

Using our growing prime list as part of the solution:

primes = [2]

for number in range(3, 9999999 + 1, 2):  # only test odd numbers

    for prime in primes:
        if prime * prime > number:  # we're past sqrt, a prime!
            primes.append(number)
            break

        if number % prime == 0:  # a composite
            break

print(*primes[:10], '...', *primes[-10:])

Nowhere as fast as @ClockSlave's sieve, but will likely finish before many of the other solutions.

Answer 4

The easiest way to do this is to use something called as Sieve. Here's how to get all the primes upto one million.

def mark_sieve(sieve, x):
    for i in range(x+x, len(sieve), x):
        sieve[i] = False

sieve = [True]*(10**7+1)
for x in range(2, int(len(sieve)**0.5 + 1)):
    if sieve[x]: mark_sieve(sieve, x)

The idea is that we initially create a list called sieve and assign all values to True which means that we are for now considering all numbers to 1 million(inclusive) as primes. We will iterate over every number to one million and mark every multiple of it as False in the sieve list. Additionally, to optimize, we iterate only to the square root of 1 million. Why so? Because a number can't have two factors both of which are greater than the square root of the number. So if we divide a number by integers till the ceiling of its square root and its still indivisible, that means its a prime.

So if you want to check if a number is prime, you can simple use sieve[some_number]. If it returns False its not a prime. To get a list of primes you can use [x for x in range(len(sieve)) if sieve[x]]

EDIT Speed comparisons -

import timeit
import math

def isPrime(number):
    if number<=1:
        return False
    if number==2:
        return True
    if number%2==0:
        return False
    for ind in range(3,int(math.sqrt(number))+1):
        if number%ind==0:
            return False
    return True

def mark_sieve(sieve, x):
    for i in range(x+x, len(sieve), x):
        sieve[i] = False


# Other approaches
time_0 = timeit.default_timer()
primes = []
for i in range (1, 10**6+1):
    if isPrime(i) == True:
        primes.append(i)
    else:
        continue

# Sieve Approach
time_1 = timeit.default_timer()
sieve = [True]*(10**6+1)
sieve[0] = False #because we wont consider zero and one as primes
sieve[1] = False
for x in range(2, int(len(sieve)**0.5 + 1)):
    if sieve[x]: mark_sieve(sieve, x)

primes_2 = [x for x in range(len(sieve)) if sieve[x]]

time_2 = timeit.default_timer()
time_1-time_0 # 12.423080921173096 seconds
time_2-time_1 # 0.9901950359344482 seconds

For a 100 thousand numbers, using sieves is more than 12 times faster. For a million that ratio becomes 90. Also, when using that many number of numbers, I would advise against appending lists. Instead, initiate a list and then assign values.