My prime number generation program in Python

Question

So I did my own take (I wrote my own algorithm) for generating prime numbers from 1 to 1000.

lst = [y for y in range(1000)]
for i in range(0,len(lst)):     #i = 1 and i is traversal
    print("iterate - " + str(i))
    for j in range(i,0,-1):     #divisor range
        print(j)
        if j != 1 and j < lst[i] and lst[i] % j == 0:
            if j in lst:
                lst[i] = 0
                break

for k in range(len(lst)):
    if 0 in lst:
        lst.remove(0)
        if 1 in lst:
            lst.remove(1)
        
        
        
print(lst)

My concerns are

• Is this code easy to read?
• Is this optimal (I don't think so)?
• What should I do for improving my code?

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

Answer 1

I am not a professional Python developer, so I will address only the performance issue: judging from you for loops structure, it seems that the running time of your implementation is \$\Theta(n^2)\$, where \$n\$ is the prime limit. However, you can do the same in \$O(n \log n)\$, or even, \$O(n \log \log n)\$ time. (See below.)

import math
import time


def op_sieve(limit):
    lst = [y for y in range(limit + 1)]
    for i in range(0, len(lst)):  # i = 1 and i is traversal
        for j in range(i, 0, -1):  # divisor range
            if j != 1 and j < lst[i] and lst[i] % j == 0:
                if j in lst:
                    lst[i] = 0
                    break

    for k in range(len(lst)):
        if 0 in lst:
            lst.remove(0)
            if 1 in lst:
                lst.remove(1)
    return lst


def sieve(limit):
    s = [True for i in range(limit + 1)]
    s[0] = s[1] = False

    for i in range(4, limit + 1, 2):
        s[i] = False

    for i in range(3, math.floor(math.sqrt(limit)) + 1, 2):
        if s[i]:
            for m in range(2 * i, limit + 1, i):
                s[m] = False

    primes = []
    prime_candidate = 0
    for i in s:
        if i:
            primes.append(prime_candidate)
        prime_candidate += 1

    return primes


def sieve2(limit):
    s = [True for i in range(limit + 1)]
    s[0] = s[1] = False

    for i in range(2, math.floor(math.sqrt(limit)) + 1):
        if s[i]:
            for j in range(i * i, limit + 1, i):
                s[j] = False

    primes = []
    prime_candidate = 0
    for i in s:
        if i:
            primes.append(prime_candidate)
        prime_candidate += 1

    return primes


def millis():
    return round(time.time() * 1000)


limit = 5000

start = millis()
original_sieve = op_sieve(limit)
end = millis()

print(end - start)

start = millis()
my_sieve = sieve(limit)
end = millis()

print(end - start)

start = millis()
my_sieve2 = sieve2(limit)
end = millis()

print(end - start)

#print(original_sieve)
#print(my_sieve)
#print(my_sieve2)
print("Agreed: ", original_sieve == my_sieve and my_sieve == my_sieve2)

The output might be as follows:

7199
2
2
Agreed:  True

Hope that helps.

Answer 2

PEP 8

Is the code easy to read?

No, it violates the Style Guide for Python Code in a few areas.

Commas should be followed by a space. Eg, range(0,len(lst)) should be range(0, len(lst)), and range(i,0,-1) should be range(i, 0, -1).

For throw-away varables, you should use _. Since k is not used in the loop for k in range(len(lst)):, you should write for _ in range(len(lst)): instead.

lst is not the best variable name. It is a list, fine, but a list of what? candidates might be a better name.

Using for index_variable in range(0, len(some_list)): is an anti-pattern in Python. It is better to enumerate directly over the container. If the index into the container is required, then you should iterate over enumerate(some_list) instead.

candidates = [candidate for candidate in range(1000)]
for index, candidate in enumerate(candidates):
    for divisor in range(candidate, 0, -1):
        if divisor != 1 and divisor < candidate and candidate % divisor == 0:
            if divisor in candidates:
                candidates[index] = 0
                break

for _ in range(len(candidates)):
    if 0 in candidates:
        candidates.remove(0)
        if 1 in candidates:
            candidates.remove(1)

print(candidates)

Optimization

Is this optimal (I don't think so)?

No, it is not optimal.

You have a list of candidates (lst), an index into the list i, and the candidate value itself lst[i]. It should be clear that your candidate values and indices are actually equal (i == lst[i]), at least before you zero out non-prime values. So we could simplify the first loop, eliminating the extra index.:

candidates = [candidate for candidate in range(1000)]
for candidate in candidates:
    for divisor in range(candidate, 0, -1):
        if divisor != 1 and divisor < candidate and candidate % divisor == 0:
            if divisor in candidates:
                candidates[candidate] = 0
                break

Next, consider you divisor range. You test divisor != 1 and divisor < candidate. Why? Because you loop over range(candidate, 0, -1) which includes both 1 and candidate. A simple modification to the limits eliminates the need to check for those:

candidates = [candidate for candidate in range(1000)]
for candidate in candidates:
    for divisor in range(candidate - 1, 1, -1):
        if candidate % divisor == 0:
            if divisor in candidates:
                candidates[candidate] = 0
                break

I'm not sure what the point of the divisor in candidates test is for, but it is not optimal. If divisor in candidates is True, which necessitates an \$O(n)\$ search through the list, then candidates[divisor] != 0 will be True, which is a \$O(1)\$ lookup.

But wait! If we test 4, we discover it is divisible by 2, and zero it out. Later, when we test 8, we discover it is divisible by 4 ... but 4 in candidates is False, so the search goes on until we discover that 8 is divisible by 2 which is in the candidates list. Does it matter that 4 was not prime? No.

candidates = [candidate for candidate in range(1000)]
for candidate in candidates:
    for divisor in range(candidate - 1, 1, -1):
        if candidate % divisor == 0:
            candidates[candidate] = 0
            break

Also, you'd actually eliminate composite numbers faster by searching divisors in ascending order.

candidates = [candidate for candidate in range(1000)]
for candidate in candidates:
    for divisor in range(1, candidate):
        if candidate % divisor == 0:
            candidates[candidate] = 0
            break

Finally, if you want to do something if some condition is True for any value in a list/range, you can use any().

candidates = [candidate for candidate in range(1000)]
for candidate in candidates:
    if any(candidate % divisor == 0 for divisor in range(1, candidate)):
        candidates[candidate] = 0

The any() loop short-circuits and stops at the first True condition, which means you don't have to break out of the inner loop yourself.

See other answers about filtering the 0 and 1 values out of the candidates list.

Answer 3

Remove print statements

Printing to the console takes a significant amount of time, and you are printing for every iteration and every element in the list. Run it once with the statements, and once without. It's a substantial time save.

Removing elements

For every iteration in the second loop, you check if 1 is there. When in reality, you just need to remove the first element of the loop. Second, you can use list comprehension to shorten the amount of code you have to write.

lst = [x for x in lst if x != 0][1:]

The first set of brackets is the list comprehension, while the [1:] is using pythons list slicing. What this does is takes the result of the list comprehension, and slices off the first element while keeping everything else. Here is a Stack Overflow answer that describes this perfectly.

Answer 4

Style

• Wrap your code in one or more clearly named functions. For example, print(primes_up_to(1000)), or is_prime(38)
• Remove the print statements
• Don't call your variables i, j, and k. Use descriptive names like possible_prime and test_divisor
• Start your divisor test list at 2, instead of checking whether the divisor is 1 each loop.
• Similarly, start your test prime list at 2, instead of removing 0 and 1 afterwards. You should generally try to avoid doing things and then undoing them. Just don't do them to begin with, it's much clearer.

Efficiency

Remove the print statements (they will slow things down quite a bit)

Yes, this is not as efficient as possible. If you want to make things faster, you can speed things up more or less as much as you want, putting in more and more effort--this is a fairly famous problem, so there's plenty to read about it elsewhere. Here are some common optimizations people might do.

• Rather than having a list of 1000 numbers, marking some of them 0, and then removing them, build up your list gradually with only things you won't remove. Also, removing an item from the middle of a list in Python is somewhat slow.
• Iterate through divisors in positive order, not reverse order. Something is more likely to be divisible by 2 than divisible by 429, so you should check that first.
• If you are testing whether 100 is prime, you only need to check divisors up to 10 (the square root). If it's divisible by say, 50, 100/50 = 2, so it will be divisible by a smaller number (2) as well. The cutoff is 100/10 = 10, where the numbers exactly match.
• If you want, you can only check prime numbers for divisibility. You don't need to check divisibility by 4 if you've already checked 2. Just keep a list of prime numbers so far, and check all the primes up to 10, instead of all the numbers up to 10.
• This gets you 'trial division', a reasonably fast way to check if ONE number is prime. But since you're checking all 1000 numbers, there are some more tricks you can do.
• For example, you can check only odd numbers to start with, or only numbers ending in 1, 3, 7, and 9, etc etc
• You could go read about the Sieve of Eratosthenes, discussed I believe in one of the other answers, which is an even faster option. I'm not sure where exactly this sieve starts being faster than trial division, but it's probably around 100-1000. It will be faster for all primes up to 1,000,000 for sure.