Finding the 10001st prime - how to optimize?

Question

Project Euler problem 7 says:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?

Here's the code I've written in Python:

def primes(n):
    primes = []
    attempt = 3
    while len(primes) < (n-1):
        for i in range(len(primes)):
            if attempt % primes[i] == 0:
                attempt += 2
                break
        else:
            primes.append(attempt)
            print (primes)
    return (primes)

While testing a number, if it finds that the number is divisible by one of the primes in the list, the for loop breaks, and starts again with a larger number. If it isn't divisible, it's added to the list of primes. This keeps going until the list is as large as desired (in this case 10000, and I've omitted 2 so the last member of the list is the 10001st prime)

The problem is that this is extremely SLOW. I've seen other solutions that can apparently solve this is seconds, if not less. What are some ways I could make this fun faster?

Searching for the term "Prime sieve" may give you useful results. — Kevin, Sep 01 '15 at 14:13
[Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) — Bhargav Rao, Sep 01 '15 at 14:14
Also, just a simple change to numerics using `numpy` will speed up things, do not use that for-loop, go by other means. — nickpapior, Sep 01 '15 at 14:15
You should post this on [codereview.se], and/or post about an algorithm on [cs.se]. — Cyphase, Sep 01 '15 at 14:19
@NicholasHassan [NumPy](https://pypi.python.org/pypi/numpy) is used for high-speed numerical solutions in Python. — Mast, Sep 01 '15 at 14:21
You mustn't try all prime divisors, but stop when you reach the square root of the attempted number. This is a significant saving. — , Sep 02 '15 at 10:08

score 1 · Answer 1 · answered Sep 01 '15 at 18:21

These are optimizations problems, so you don't want to be printing every time you update the list. The other thing is don't use list at all because is not very memory efficient. You should use instead generators. Its very fast and you don't get to consume memory using lists. Below is a code for this purpose, watch how the yield keyword is being used in order to convert count_primes function into a generator.

def is_prime(num):
    """
    Checks if a number is prime
    """
    prime_counter = 1
    for x in range(1, num):
        if num % x == 0:
            prime_counter += 1
        if prime_counter > 2:
            return False
    return True


def count_primes():
    """
    Counts primes until PRIMES_TO_COUNT
    is reached
    """
    PRIMES_TO_COUNT = 1000       # Modify this value
    prime_counter_num = 0
    start_point_num = 1
    while True:
        if is_prime(start_point_num):
            if prime_counter_num == PRIMES_TO_COUNT:
                yield start_point_num
                print "This is the %dth prime number: %s" \
                      % (prime_counter_num, start_point_num)
                break
            prime_counter_num += 1
        start_point_num += 1


if __name__ == '__main__':
    for prime_number in count_primes():
        print prime_number

Hope this helps you!. Python generators!

score 0 · Answer 2 · answered Jan 01 '17 at 15:13

0

Instead of checking for every odd number you can check for all numbers of the form 6n±1 because all primes are of that form.

answered Jan 01 '17 at 15:13

ashenoy

163
1
9

I don't know why this is downvoted but it contains interesting information. The only two exceptions on this rule are 2 and 3. See http://mathworld.wolfram.com/PrimeNumber.html – kvantour Jul 22 '18 at 20:14

Finding the 10001st prime - how to optimize?

2 Answers2

Linked