Euler 3

Since last night I've had a spark. I thought of a different way to do it instead of counting down.
Beware people who plan on doing Euler problem 3 anytime soon, this is most likely spoil it for you. If you want to do it on your own, I suggest stopping here and waiting for my next Euler post to not look at.








Alright, so before I was counting down from the number 600851475143 / 2, which I realized I didn't need to do. I thought instead, that I'd count up from 2 and divide 600851475143 by the first number that evenly divided it, and was prime. While that was half of the speed up, I also made myself a more efficient 'isPrime(n)' function.


My old code would be something like (it's about to get Pythony up in here!):

def isPrime(n):
        isPrimeBool = True
        check = n / 2
        while check > 1:
                if n % check == 0:
                        isPrimeBool = False
                        break
                check -= 1
        return isPrimeBool

Now that would work perfectly fine, but it takes a LONG time to execute with big numbers. Since it goes through every single number below n / 2. I came up with an optimized version which runs about 10 times fast:

def isPrime(inNum):

        checkNum = 2

        while checkNum * checkNum <= inNum:

                if inNum % checkNum == 0:

                        return False

                checkNum += 1

        return True

The two major differences here is that it goes only to inNum's square root, and that it counts up from 2. So if a number is even, then it immediately pushes out a False value.
While optimizing the isPrime function was helpful, the real key came from how I was finding the nubmers to pass to isPrime. In all reality, I optimized it in a similar way.

I made it so it counts up from 2, and checks if the number (which starts as 600851475143) is divisible by the counter, and if the counter is prime. If the counter is prime and it's divisible then the max number gets divided by the counter, and the counter resets to 2. The exact code is:

num = 600851475143

check = 2 

while check < num:

        if num % check == 0 and isPrime(check):

                num /= check

                check = 2 

        check += 1

print(num)

So I've solved it (I'm not giving you the answer, if you wanna get it just copy and paste my code), but Project Euler seems to hate me. It wont let me enter it due to not putting the captcha in correctly (which I am). So I'm stuck with having an answer and no credit.

Also, on a side note, er, on two side notes:

-Python is a wonderful language, it doesn't matter if you have no former programming experience, it's just a fucking amazing language to learn.

-The Glitch Mob <3


P.S.
Blogger's auto-formatting makes me die inside.