0

I'm very new and I'm not sure if i'm just stupid but I thought it try and just ask. I created a list with all numbers from 2 up to n. Then it should start with the 2, cross out all the numbers that are divisible by to form the list. Then 3 do the same. 4 should be crossed off. 5 and so on. but 3 gets crossed off and the output list is all wrong and I can't figure out why.

here's my code

n=10
list = []
primes_up_to_n = []
p = 0

for z in range(n):
    if z > 0:
        list.append(z+1)

for i in list:
    primes_up_to_n.append(i)
    for t in list:
        if t % i == 0:
            list.remove(t)
print(primes_up_to_n)
leon braga
  • 3
  • 2

2 Answers2

0

Don't remove items from lists as you are iterating over them, it will cause the iteration to skip over items you don't want it to.

Instead, let's have a list where index 0 represents the number 2 and we just replace non-prime values with None. We can also use the step of the range function to only visit candidates we know are divisible by the prime.

prime_candidates = list(range(2, n+1))
for index, prime in enumerate(prime_candidates):
    if prime is None:
        continue  # Ignore non-primes in our list
    for candidate_index in range(index+prime, len(prime_candidates), prime):
        # range(index+prime, len(prime_candidates), prime)
        # For each prime p, we start at 2p and mark it non-prime
        # We then do the same for Np for each N until we pass the size of our list
        prime_candidates[candidate_index] = None

print([prime for prime in prime_candidates if prime])
Patrick Haugh
  • 59,226
  • 13
  • 88
  • 96
0
# Python program to print all
# primes smaller than or equal to
# n using Sieve of Eratosthenes


def SieveOfEratosthenes(n):

    # Create a boolean array
    # "prime[0..n]" and initialize
    # all entries it as true.
    # A value in prime[i] will
    # finally be false if i is
    # Not a prime, else true.
    prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):

        # If prime[p] is not
        # changed, then it is a prime
        if (prime[p] == True):

            # Update all multiples of p
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1

    # Print all prime numbers
    for p in range(2, n+1):
        if prime[p]:
            print(p)


# Driver code
if __name__ == '__main__':
    n = 20
    print("Following are the prime numbers smaller"),
    print("than or equal to", n)
    SieveOfEratosthenes(n)

Answer Source

Asher
  • 11