Euler Project, #7 - Python

Question

So I'm trying to find the 10,001st prime #. Here's my code -

counter = 3
primes = [1]

while len(primes) < 10002:
    for i in range(2, counter):
        if counter % i == 0:
            counter += 1
    else:
        primes.append(counter)
        counter += 1

print counter

So what I get as an output in primes is a list of numbers, the first few numbers are 1, 3, 5, 7, 11... so far, so good... 13, 17, 19, 23, 27... wait, 27? So at that point it breaks down and starts returning mostly primes but not all primes. And it takes forever.

I'm new to programming, made it through CodeAcademy's Python course and now trying to figure out how to get past what was essentially just an introduction to the grammar. I don't come from a math background, so while I know what a prime is, I know there are far better ways to go about this. If there's anyone in a similar boat who wants to "partner up" and work together on learning Py2.7, I'm more than happy to.

Answer 1

Here is my solution to this problem. It may not be so quick but it is not precisely for problem 7.

import time
start = time.time()

n = int(input('Please enter a number: '))
def nth_prime(n):
    primes = [2]
    x = 3
    max_amount = int(input('How much would you like to go for?: '))
    while True:
        try:
            while x < max_amount:
                for i in primes:
                    if x % i == 0:
                        break
                else:
                    primes.append(x)
                x += 2
            print(primes[n])
        except IndexError:
            max_amount = int(input("Please enter a greater number: "))
            continue
        else:
            print(f('Good job. You\'ve found the {n+1}st prime number :) ')
            break
nth_prime(n)

end = time.time()
print(str(float(end - start)) + " seconds")

Answer 2

import time
start_time = time.time()

def is_prime(limit):
    aval = True
    for j in range(2,int(limit**0.5)+1):
        if limit == 2:
            aval = True
            break
        elif limit % j == 0:
            aval = False
            break
    return aval
counter = 0
for i in range(2,1000000):
    if is_prime(i):
        counter += 1
        if counter == 10001:
            print("the 10001th prime number is: ",i)
            break

print("seconds: ", time.time() - start_time)

Answer 3

If you want to write an efficient and smart code, you may use the Sieve of Eratosthenes, a good algorithm for finding prime numbers in a given range. For more information, read this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 4

As an exercise for you instead of writing for you a simple step by step code I will write a complex line of code with a solution to a similar problem.

Try to figure out what is going on here in this line as an exercise to understand python. This code will find the prime numbers until n number not the first n prime numbers that you want

def primes(n):
   return sorted(set(range(2, n+1)) - set([p*i for p in range(2, n+1) for i in range(p, n+1)]))

Answer 5

Since you're doing a project Euler puzzle, you obviously want comments on your code rather than the solution.

Your code:

counter = 3
primes = [1]

while len(primes) < 10002:
    for i in range(2, counter):
        if counter % i == 0:
            counter += 1
    else: # Mis-aligned else (assuming it's intended for the if)
        primes.append(counter)
        counter += 1

print counter

1. Your else is mis-aligned with the if
2. Your for loop goes all the way to counter, and testing divisibility against itself is bound to find remainder 0.
3. Your else clause will hit for each non-factor of counter. Most numbers will not be a factor, so you don't want to take action in that case. Instead break out of the loop when the if part triggers.
4. After exiting the for loop, you'll want to check if a factor was found and if not, add counter to your list of primes.

Looks like you are trying to implement a naive un-optimized brute force search, and that is fine.

Maybe try and write out the algorithm in words or pseudo code before coding it.

Answer 6

I won't implement anything for you, since that's why you're doing Project Euler, but I will point you strongly in the direction of The Sieve of Eratosthenes. It will calculate in seconds what your code will do in hours.

It works as such: (in pseudocode)

for known_prime in a huge list of numbers:
    k=2
    while known_prime*k < the biggest number:
        known_prime*k is not prime
        k += 1

Once you've made it through sqrt of the list, you've found every prime number within the list.