Sieve of Eratosthenes - Finding Primes Python

You're not quite implementing the correct algorithm:

In your first example, primes_sieve doesn't maintain a list of primality flags to strike/unset (as in the algorithm), but instead resizes a list of integers continuously, which is very expensive: removing an item from a list requires shifting all subsequent items down by one.

In the second example, primes_sieve1 maintains a dictionary of primality flags, which is a step in the right direction, but it iterates over the dictionary in undefined order, and redundantly strikes out factors of factors (instead of only factors of primes, as in the algorithm). You could fix this by sorting the keys, and skipping non-primes (which already makes it an order of magnitude faster), but it's still much more efficient to just use a list directly.

The correct algorithm (with a list instead of a dictionary) looks something like:

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

(Note that this also includes the algorithmic optimization of starting the non-prime marking at the prime's square (i*i) instead of its double.)

Printing prime number between a range. Sieve of Eratosthenes

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]

Sieve of Eratosthenes - Primes between X and N

The implementation you've borrowed is able to start at 3 because it replaces sieving out the multiples of 2 by just skipping all even numbers; that's what the 2*… that appear multiple times in the code are about. The fact that 3 is the next prime is also hardcoded in all over the place, but let's ignore that for the moment, because if you can't get past the special-casing of 2, the special-casing of 3 doesn't matter.

Skipping even numbers is a special case of a "wheel". You can skip sieving multiples of 2 by always incrementing by 2; you can skip sieving multiples of 2 and 3 by alternately incrementing by 2 and 4; you can skip sieving multiples of 2, 3, 5, and 7 by alternately incrementing by 2, 4, 2, 4, 6, 2, 6, … (there's 48 numbers in the sequence), and so on. So, you could extend this code by first finding all the primes up to x, then building a wheel, then using that wheel to find all the primes between x and n.

But that's adding a lot of complexity. And once you get too far beyond 7, the cost (both in time, and in space for storing the wheel) swamps the savings. And if your whole goal is not to find the primes before x, finding the primes before x so you don't have to find them seems kind of silly. :)

The simpler thing to do is just find all the primes up to n, and throw out the ones below x. Which you can do with a trivial change at the end:

primes = numpy.r_[2,result]
return primes[primes>=x]

Or course there are ways to do this without wasting storage for those initial primes you're going to throw away. They'd be a bit complicated to work into this algorithm (you'd probably want to build the array in sections, then drop each section that's entirely < x as you go, then stack all the remaining sections); it would be far easier to use a different implementation of the algorithm that isn't designed for speed and simplicity over space…

And of course there are different prime-finding algorithms that don't require enumerating all the primes up to x in the first place. But if you want to use this implementation of this algorithm, that doesn't matter.

Sieve of Eratosthenes in Python

"I am told I need to use square root". Why do you think that is? Usually the sieve of E. is used to remove all "non prime" numbers from a list; you can do this by finding a prime number, then checking off all multiples of that prime in your list. The next number "not checked off" is your next prime - you report it (with yield), then continue checking off again. You only need to check for factors less than the square root - factors greater than the square root have a corresponding factor less than the square root, so they have alread been found.

Unfortunately, when it comes to printing out the primes, you can't "stop in the middle". For example, 101 is prime; but if you only loop until 11, you will never discover that it's there. So there need to be two steps:

1) loop over all "possible multiples" - here you can go "only up to the square root"

2) check the list for all numbers that haven't been checked off - here you have to "go all the way"

This makes the following code:

def p(n):
  is_p=[False]*2 + [True]*(n-1)
  for i in range(2, int(n**0.5)):
    if is_p[i]:
        for j in range(i*i, n, i):
            is_p[j] = False
  for i in range(2, n):
    if is_p[i]:
      yield i

print list(p(102))

The result is a list of primes up to and including 101.

Prime numbers in a given range using Sieve of Eratosthenes

The end point in a range() is not included. Since sqrt(10) is 3.1623, your range() loops to 2 and no further, and the multiples of 3 are not removed from your list. Your code works for 100, because it doesn't matter if you test for multiples 10 (those are already covered by 2 and 5).

The same issue applies to your other loops; if you want to include n itself as a candidate prime number you should also include it in the other ranges.

Note that you also want to ignore 0 and 1, those are not primes. You could add A[0] = A[1] = False at the top to make sure your last loop doesn't include those, or start your last loop at 2 rather than 0.

You want to add one to the floored square root to make sure it is tested for:

for i in range(2, int(sqrt(n)) + 1):

I'd use booleans rather than 0 and 1, by the way, just for clarity (there is not much of a performance or memory footprint difference here):

def prime_numbers(n):
    sieve = [True] * (n + 1)  # create a list n elements long
    for i in range(2, int(sqrt(n)) + 1):
        if sieve[i]:
            for j in range(i * 2, n + 1, i):
                sieve[j] = False
    for i in range(2, n + 1):
        if sieve[i]:
            print(i)

I used [..] * (n + 1) to create a list of n items (plus 0); this produces a list with n shallow copies of the contents of the left operand. That's faster than a list comprehension, and the shared references are fine since True is a singleton in Python.

Demo:

>>> prime_numbers(31)
2
3
5
7
11
13
17
19
23
29
31

Note that 31 is included there; your code would have resulted in incorrect output as you'd have left in all the multiples of 5.

python prime numbers Sieve of Eratosthenes

An old trick for speeding sieves in Python is to use fancy ;-) list slice notation, like below. This uses Python 3. Changes needed for Python 2 are noted in comments:

def sieve(n):
    "Return all primes <= n."
    np1 = n + 1
    s = list(range(np1)) # leave off `list()` in Python 2
    s[1] = 0
    sqrtn = int(round(n**0.5))
    for i in range(2, sqrtn + 1): # use `xrange()` in Python 2
        if s[i]:
            # next line:  use `xrange()` in Python 2
            s[i*i: np1: i] = [0] * len(range(i*i, np1, i))
    return filter(None, s)

In Python 2 this returns a list; in Python 3 an iterator. Here under Python 3:

>>> list(sieve(20))
[2, 3, 5, 7, 11, 13, 17, 19]
>>> len(list(sieve(1000000)))
78498

Those both run in an eyeblink. Given that, here's how to build an is_prime function:

primes = set(sieve(the_max_integer_you_care_about))
def is_prime(n):
    return n in primes

It's the set() part that makes it fast. Of course the function is so simple you'd probably want to write:

if n in primes:

directly instead of messing with:

if is_prime(n):

Understanding Sieve of Eratosthenes in Python

That code is an attempt at using trial division to produce a sequence of primes.

To correct it:

pp = 2
ps = [pp]
lim = raw_input("Generate prime numbers up to what number? : ")
while pp < int(lim):
    pp += 1
    for a in ps:
        if pp%a==0:
            break
    else:                # unindent
        ps.append(pp)    #  this

To make it much more efficient (in fact, optimal) trial division:

pp = 2
ps = [pp]
lim = raw_input("Generate prime numbers up to what number? : ")
while pp < int(lim):
    pp += 1
    for a in ps:
        if a*a > pp:         # stop
            ps.append(pp)    #  early
            break
        if pp%a==0:
            break

Why this sieve method of finding primes is slower than a brute force

Among other things, getXPrimes isn't actually finding primes (you only test divisibility by multiples of 2, which no odd number will ever fail), while getXPrimesSieve is, so you're comparing apples and oranges.

Beyond that getXPrimesSieve isn't doing much to improve performance, and is doing stuff that hurts it; it still has to perform many remaindering operations (a good sieve wouldn't); while it tries to avoid testing numbers above the square root of the number being tested, it does so by recomputing that square root for every prime to test, which is far more expensive than doing it once up front, as in getXPrimes.

Point is, you need to make your code both work and perform better than naive trial division. I suggest looking at useful sieving algorithms, e.g. for finding all primes up to a certain bound, the Sieve of Eratosthenes which amortizes the cost of "virtual" trial division without actually doing division or remaindering work at all, which would run considerably faster than either of your attempts.

Sieve of Eratosthenes - Finding Primes Python