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)

Well to start change `def isPrime(i):` to `def isPrime(number):` and `for i in range(3,int(sqrt(number))+1):` to `for i in range(3,int(math.sqrt(number))+1):` — jacoblaw, Aug 01 '17 at 17:20
This is a very inefficient way of calculating a list of primes. It would be better to generate the primes directly with a sieve. — AChampion, Aug 01 '17 at 17:21
Mh... does it even run? `i` should be `number`, `sqrt` should be `math.sqrt` — Andrea Corbellini, Aug 01 '17 at 17:21
When you use a for loop in Python, you are almost surely doing it wrong. The Python way is to use list comprehension: `primes = [i for i in range (1, 9999999) if isPrime(i)]`. — DYZ, Aug 01 '17 at 17:29
You are very right @DYZ that is exactly what i was going to comment as it is much more efficient than appending to an empty list and also a more concise statement — Joe Iddon, Aug 03 '17 at 06:04

Md. Rezwanul Haque · Answer 1 · 2017-08-01T17:24:25.160

4

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)

edited Aug 01 '17 at 17:24

answered Aug 01 '17 at 17:21

Md. Rezwanul Haque

2,882
7
28
45

1

Nit: `else: continue` is not necessary – Andrea Corbellini Aug 01 '17 at 17:23
fixed @AndreaCorbellini. – Md. Rezwanul Haque Aug 01 '17 at 17:25

score 2 · Answer 2 · answered Aug 01 '17 at 17:23

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]

Clock Slave · Answer 3 · 2017-08-03T07:14:17.843

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.

This approach is amazingly fast compared to the others. However, it could use a tiny bit of cleanup around the edges as it claims 0 & 1 are primes... — cdlane, Aug 02 '17 at 23:42

score 2 · Answer 4 · answered Aug 02 '17 at 23:47

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.

Alexander · Answer 5 · 2017-08-01T18:00:08.893

Using a conditional list comprehension:

primes = [
    i for i in range(1, 9999999) 
    if i == 2 
    or i > 2  # Anything less than 2 is not prime.
    and i % 2  # No evens (except for 2 above)
    and all(i % n for n in range(3, int(i ** 0.5) + 1))]

>>> primes[:10]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

>>> primes[-10:]
[9999889,
 9999901,
 9999907,
 9999929,
 9999931,
 9999937,
 9999943,
 9999971,
 9999973,
 9999991]

PythonProgrammi · Answer 6 · 2017-08-03T07:23:12.537

Now it works, I have shortned the numbers to 999

import math

primes = []


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

for i in range(1, 999):
    if isPrime(i):
        primes.append(i)

print(primes)

[OUTPUT]:

[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

score 1 · Answer 7 · answered Aug 03 '17 at 05:58

Your algorithm to get all prime numbers in [0,9999999] is not very efficient. It need spend a long time to do it so that you cannot see the output when you execute it. It is just because it has not been done. For a faster algorithm, you might check this out

Calculating Primes and Appending to a List

7 Answers7

Now it works, I have shortned the numbers to 999

Linked