0

I've been tackling project euler, very slowly. I'm on problem 7, which can be seen here: https://projecteuler.net/problem=7

Essentially you're supposed to find the 10,001st prime number. I created a function that outputs a list of an input's factors:

def factor(number):
factors = []
for i in range(1, number + 1):
    if i == number:
        factors.append(i)
    elif number % i == 0:
        factors.append(i)
return factors

Then exploited the len() function to find primes:

def prime(number):
primes = []
for i in range(1, number + 1):
    if len(factor(i)) == 2:
        primes.append(i)
print("There are {} primes below {}.".format(len(primes), number))

Now I modified this to tackle the problem at hand.

def primes(num):
primes = []
a = 0
while len(primes) < num:
    a = a + 1
    if len(factor(a)) == 2:
        primes.append(a)
print(len(primes))
print(primes[-1])

Now it worked, but it probably took 10+ minutes to run. I understand that this is because it's running through a ridiculous amount of numbers, I guess what I'm asking is what is a creative way to avoid creating a massive amount of criteria for the function to sort through? Not looking for a definitive answer, just trying to see actual coders' thought processes.

quesadyllan
  • 69
  • 1
  • 7
  • See linked question. You only need to calculate up to the square root of the number to know all the primes of that number. – dawg Jul 13 '17 at 00:23
  • I think that flag links to something else. But do check: https://stackoverflow.com/questions/21003381/program-to-find-the-nth-prime-number – Anton vBR Jul 13 '17 at 00:33
  • You do not need all the factors. Finding any factor between 1 and sqrt(num) means that num is composite. Taking a different approach, you could implement the Sieve of Eratosthenes. It will come in useful for some later problems in Project Euler. – rossum Jul 13 '17 at 12:12

0 Answers0