Printing prime number between a range. Sieve of Eratosthenes

Question

I've got all the numbers appended into list1 from x to y (inclusive). I now only need the list to contain only prime numbers from x to y inclusive

def primes(x , y):
    list1 = []
    for i in range(m, n + 1):
            list1.append(i)
    for elements in list1:
            if elements % 2 == 0:
                    pos = list1.index(elements)
                    list1.pop(pos)
    return list1

I've got all the numbers appended into list1 from x to y (inclusive) and also got rid of the even numbers but i cant seem to get rid of the other numbers that arent prime. I now only need the list to contain only prime numbers from x to y inclusive

For example x = 7, y = 23

list1 = [7, 11, 13, 17, 19, 23]

Thanks in advance

So in other words, you are at the very beginning and have trouble implementing the sieve algorithm. Please tell us what you don't understand about the sieve or/and where your troubles are trying to implement it. — timgeb, May 28 '17 at 14:26
Ive tried for elements in list1: if elements % 2 == 0: pos = list1.index(elements) list1.pop(pos) That gets rid of all the even numbers but i cant seem to get rid of the other ones that arent prime — a_student, May 28 '17 at 14:29
There are tons of question in python relative to generation of prime numbers on SO. You should have a look at them. — Nuageux, May 28 '17 at 14:31
Possible duplicate of [Sieve of Eratosthenes - Finding Primes Python](https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python) — C4stor, May 29 '17 at 12:27

score 1 · Accepted Answer · answered May 28 '17 at 14:53

Here's a few tips: You don't need to generate the whole list of integer between x and y, and then remove the non-prime one. One faster approach is to generate all the prime numbers smaller than y and then remove those who are smaller than x. That way you can use the previously computed prime numbers to efficiently check if a number is a prime or not.

So let's start at the beginning. 2 is the only even prime number. So you can start from 2 and iterates over the odd number till y. A number will be prime if it is not divisible by any previous prime number.

For each number between 0 and y, you start with the assumption that it is a prime number. You check if it is divisible by the previous primes. If it is a multiple of any prime number then you can stop (break) since you know it is not a prime number. If it was not a multiple of any previous prime, then you add it to the list of prime numbers.

Finally once you have your list of prime numbers between 0 and y, you remove the elements smaller than x.

Which gives in Python:

def primes(x , y):
    l = [2] # list of prime numbers
    for n in range(3,y+1,2): # iterations over odd numbers
        isprime = True
        for e in l:
            if n % e == 0:
                isprime = False
                break
        if(isprime):
            l.append(n)

    return [e for e in l if e >= x]

print(primes(7,23))
# [7, 11, 13, 17, 19, 23]

Printing prime number between a range. Sieve of Eratosthenes

1 Answers1