Skip to main content
candidate-1 to candidate correction applied to second place
Source Link
AJNeufeld
  • 35.3k
  • 5
  • 41
  • 103
candidates = [candidate for candidate in range(1000)]
for candidate in candidates:
    if any(candidate % divisor == 0 for divisor in range(1, candidate - 1)):
        candidates[candidate] = 0
candidates = [candidate for candidate in range(1000)]
for candidate in candidates:
    if any(candidate % divisor == 0 for divisor in range(1, candidate - 1)):
        candidates[candidate] = 0
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
Grammar, candidate - 1 not necessary when candidate used as end of range
Source Link
AJNeufeld
  • 35.3k
  • 5
  • 41
  • 103

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 simplysimplify the first loop, eliminating the extra index.:

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

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 simply the first loop, eliminating the extra index.:

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

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(1, candidate):
        if candidate % divisor == 0:
            candidates[candidate] = 0
            break
Source Link
AJNeufeld
  • 35.3k
  • 5
  • 41
  • 103

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 simply 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 - 1):
        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 - 1)):
        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.