Finding Primes

[Peter Farrell]

Ever look for prime numbers in math class? Good job for a computer! The first step is brute force, but here's how a couple of students and I found ten thousand (and one) primes and timed our programs to speed up our code 150 times. It took some good old-fashioned mathematical thinking to rule out a whole bunch of numbers.

http://hackingmathclass.blogspot.com/2016/03/prime-testing.html

Peter Farrell

[kirby urner]

Looking good.

Remember if you're appending primes to a list, then it also makes sense to only divide by smaller primes up to sqrt, when testing a next number

i.e. rather than test-divide by all odds up to sqrt(candidate), you may test-divide only by primes found so far. 

Since you're keeping the list anyway, why not?

A generator function showing trial-by-division:

def Primes_gen():
    yield 2
    _primes_so_far = [2]
    candidate = 1
    while True:
        candidate += 2
        limit = sqrt(candidate)
        for prev in _primes_so_far:
            if prev > limit:
                _primes_so_far.append(candidate)
                yield candidate
                break
            if not candidate % prev:
                break

Lets time it:

import time
start = time.time()
p = Primes_gen()
for _ in range(10000):
    next(p)
print(next(p))  # 10001st prime
end = time.time()
print(end-start)

OUTPUT:
104743
0.2798950672149658

Kirby

https://en.wikibooks.org/wiki/Some_Basic_and_Inefficient_Prime_Number_Generating_Algorithms

[Oleg Gleizer]

Hi Peter,

Could using Eratosthenes sieve be faster?

Oleg Gelizer

--
You received this message because you are subscribed to the Google Groups "MathFuture" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mathfuture+...@googlegroups.com.
To post to this group, send email to mathf...@googlegroups.com.
Visit this group at https://groups.google.com/group/mathfuture.
For more options, visit https://groups.google.com/d/optout.

[Peter Farrell]

Hi, Kirby, I was trying to get a generator to keep going through the list. Thanks a lot for the code!

[Peter Farrell]

Hi, Oleg, 

It seems like it would, but the attempts using my advanced beginner Python are much, much slower! This only checks the numbers up to 100,000, and it takes 5 seconds:

def eratsieve(num):

    '''creates a list of primes up to n using Eratosthenes' sieve'''

    #first create a list of all the numbers up to num

    list1 = [n for n in range(2,num)]

    #now change all the multiples of each number to 'X'

    for i in range(2,int(sqrt(num))):

        for v,j in enumerate(list1):

            if type(j) == int and j % i == 0  and j > i:

                list1[v] = 'X'

    primes = [x for x in list1 if x != 'X']

    return primes

        

primes = eratsieve(100000)

print(primes[-1])

99991

5.042832851409912

Peter