Problem 3

For questions about problems on the Project Euler web site. No spoilers. Please include the question number in the subject line of your post.

Problem 3

Postby Dikkedar » Tue Aug 09, 2016 3:14 pm

Hello everyone, first post here.

I'm a physics student and am very, very new to python, and I am having problems with the third Euler problem.

Instead of making a program to find the largest prime factor of the huge number in the problem, I tried generalizing it so that my program takes an input and prints the largest prime factor of that input.

I created what I thought would give me a correct answer, but when running, it does not respond when i input a value such as 10 or 14, for example.

Since I'm new, my goal was not to write the code in the most ergonomical way, but to just get the right answer. So I'm sorry if the code is messy and longer than it has to be. Can anyone see the problem?

Code: Select all
#Project Euler Problem 3
#What is the largest prime factor of the number 600851475143?

#Goal is to find prime factors of a given number.
#I will try to collect the prime factors in a list.

number = int(input("Enter a number to find its largest prime factor: "))

primefactors = []
prime = 2

num = 3
div = 2

while number >= prime:
    #Continues dividing with the prime factor until it is not divisible anymore.
    #Adds the prime as a prime factor for each succesful division.
    while number % prime == 0:
        primefactors.append(prime)
        number = int(number / prime)

    #Change the value of the prime variable to the next prime integer.
    while div <= num:
        if div == num:
            #num is a prime if the loop cycles through all values of div up to num.
            prime = num
            break
        elif num % div == 0:
            #If num is not a prime, add 1 to num and check again.
            num += 1
            continue
        else:
            div += 1
            continue

largestprimefactor = max(primefactors)

print(largestprimefactor)
Last edited by Yoriz on Tue Aug 09, 2016 4:41 pm, edited 1 time in total.
Reason: First post lock.
Dikkedar
 
Posts: 1
Joined: Tue Aug 09, 2016 2:58 pm

Re: Problem 3

Postby ichabod801 » Tue Aug 09, 2016 10:42 pm

The problem is in your code finding primes.

Say you have 10 as your number. You take the starting prime factor of 2 out and you have 5 left. So you check for the next prime with div = 2 and num = 3. 2 != 3 and 3 % 2 != 0, so div becomes 3. 3 == 3 so you change prime to 3. 3 is not a factor of 5, so you check for the next prime. Well, you left it as div = 3 and num = 3. So 3 == 3 and prime is set to 3, and you have an infinite loop checking that 3 is not a factor of 5.

Note that to find the next prime, you either need to know all the primes before it, or you need to check starting from 1 each time. The first solution is not only much more economical, it's the only one that's going to work with some of those Euler problems.
Due to the reasons discussed here we will be moving to python-forum.io on October 1st, 2016.
This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.
ichabod801
 
Posts: 688
Joined: Sat Feb 09, 2013 12:54 pm
Location: Outside Washington DC

Re: Problem 3

Postby Ofnuts » Wed Aug 10, 2016 9:20 am

Dikkedar wrote:Since I'm new, my goal was not to write the code in the most ergonomical way, but to just get the right answer. So I'm sorry if the code is messy and longer than it has to be. Can anyone see the problem?


Since you are new: the answer is (at least partly) in your question... You cannot see the problem because your code is messy. Good programmers aren't more clever (and hardly more knowledgeable) than you. They just learned to have a very clear idea of what the code should do before even writing it down, and to write clear and clean code. Then debugging is easy.
This forum has been moved to http://python-forum.io/. See you there.
User avatar
Ofnuts
 
Posts: 2659
Joined: Thu May 14, 2015 9:46 am
Location: Paris, France, EU, Earth, Solar system, Milky Way, Local Cluster, Universe #32987440940987


Return to Project Euler

Who is online

Users browsing this forum: No registered users and 4 guests