Problem 003

[andrewsnell]

You don't have to give up on PHP, but running the scripts on your computer by way of the command line, rather than by uploading and using a web browser, is far more efficient in both the coding and execution phases. Also, if you are going the brute-force approach, I would recommend pairing PHP with MySQL (also running on your PC). There is nothing like running a script for hours generating numbers, just to lose everything to a glitch on the last line of your code! For example, if write up a prime-generation script with a database connection, you can let it run overnight and in the morning you will have a nice, giant table full of primey goodness. Accessing this table as an array for use in later code is pretty trivial--but extremely helpful and time-saving with later problems.

[LarryC]

As quilan says Python has a load of features but the important thing is they don't get in the way until you're ready. You don't need to learn generators to do Problem 3 for example but they sure are handy later!

I personally think Python is probably the best language to begin with.

[hk]

But the algoritm thought up would have blown up every programming language as already was suggested.

[LarryC]

Python doesn't fix poor algorithms but it helps more complicated ones be expressed easier and quicker. But I'm slowly learning Haskell at the moment; when an easy problem comes out, I'll have a go in it!

[gary]

I seem unable to submit what I am quite certain is the correct result for Problem 003. Tried both cut and paste and direct entry. Also, compared my result with some prime factor calculators that are available. My answer is something like 1097****

It was noted in discussion that a more difficult factorization occurs for the number - 1234567890123. My code correctly derived the prime factors as 116216501 3541 3.

Gary

[hk]

What you find for problem 3 is way too large.
Check that you try to factor the correct number : 600851475143.
Let your program print out this number first, before doing anything with it.

[gary]

Thank you hk. For whatever reason I was checking 600851475140, wrong last digit. Now it is accepted.

[userProjectEuler]

Hi.

My solution to problem 3 takes 7 seconds to complete. Do you think it's too much?

Thank you.

[Assato]

Hm, yes. There are much faster ways of doing it... did you read the thread for the problem that opens up after you solve it?

[userProjectEuler]

Hm, yes. There are much faster ways of doing it... did you read the thread for the problem that opens up after you solve it?

yeah I'll take a look. thanks.
nice pic. hehe

[MrMancunian]

Can someone explain the basics of prime factors? I mean, I actually don't understand how I'm supposed to know which numbers to use to find the 600851475143 and how I'm supposed to find them...

Steven

[elendiastarman]

Every number can be expressed as p1*p2*p3*...*pn, which are prime numbers, not necessarily different. For example, 3 = 3, 6 = 2*3, 18 = 2*3*3, 23=23, etc... You are asked what the largest such number is in the prime factorization of 600851475143.
This clear enough for you?

[MrMancunian]

That's clear. Now, how do I go around this? Should I work bottom up, so start with the lowest primes, or top down, starting with 600851475143?

[elendiastarman]

The largest prime factor is nowhere near as large as 600851475143. If you take a few small numbers and find its factors (not necessarily prime) and look at where the primes are, you'll see that all prime factors (but one) are less than the square root of the number being factorized. That should be enough to get you started .

[lylegood]

First off I apologize in advance for digging up this old topic, but I think I'm having a similar issue in python.
Here is my code:

Code: Select all

#initial variables
#print "This program computes the highest prime number of whatever interger suits your fancy."
#startingNumber = testingNumber = 13195  #(correct)
#startingNumber = testingNumber = ((600851475143+13195)/2)
startingNumber = testingNumber = (600851475143)
primePossibles = []

print "Starting", startingNumber

#use loop to find factors, store to list
while testingNumber >= 1:
    if startingNumber % testingNumber == 0:
        primePossibles.append(testingNumber % startingNumber)
        testingNumber = testingNumber - 1
        print primePossibles
    else:
        testingNumber = testingNumber - 1
        
print "Numbers to be tested", primePossibles

#determine which numbers are prime
testNumber = len(primePossibles) - 1 #works

while testNumber >= 0:
    pTest = 2
    print "the number being tested is ", primePossibles[testNumber], "at position ", testNumber
    #print "the first dividend wish start at", pTest
    while pTest < primePossibles[testNumber]:
        if primePossibles[testNumber] % pTest == 0: #doesnt have a remainder
            primePossibles.pop(testNumber)#pop it
            pTest = primePossibles[testNumber]
            #print "Does Have a Remainder, means it's not prime"
            #print primePossibles[testNumber]
            #print pTest
            #print
        else: #has a remainder
            pTest = pTest + 1
            #print "Doesnt Have a Remainder, next try"
            #print primePossibles[testNumber]
            #print pTest
            #print
    #print "end of prime test for", primePossibles[testNumber]
    testNumber = testNumber - 1  
    #print primePossibles
#use loop to determine largest of the prime numbers, use for loop to go through list
print primePossibles[1]

The spaces are where i was using print statements to check my work. It spits out the correct answer rather quickly (but I'm sure it could be optimized), but it gets hung up at this output when i use 600851475143:

Starting 300425744169
[0L]

Any suggestions? I dont know where to start solving this problem.

[elendiastarman]

For one, your code is mostly correct. As such, I suggest you edit it out to avoid spoiling the problem for others...

The problem with your code is that it does nothing for a long time. A very long time. For instance, on my average machine, doing a loop from 1 to 1,000,000,000 takes about 38 seconds. That number is about 600 times bigger (and as such will take about 600 times as long). As for optimizing your loop to cut out the unnecessary stuff, see my above post.

That help?

[MekeorMelire]

should i use some algorithms like these
http://en.wikipedia.org/wiki/Integer_fa ... algorithms
to solve problem 003?

or should i have my own algorithm?
do i need a list of prime numbers? - or should my program also calculate them?

[hk]

should i use some algorithms like these
http://en.wikipedia.org/wiki/Integer_fa ... algorithms
to solve problem 003?

or should i have my own algorithm?
do i need a list of prime numbers? - or should my program also calculate them?

The idea is that you try to solve these problems as good as you can by finding a way to solve them on your own.

[ClockworkMan986]

I hate to bump posts, but I have some issues.

First, I like to break down programs since I am still learning the process, and I use the examples. My first step was to figure out the factors of a max number. Here is what I have using the example number of 13,195:

Code: Select all

/*
Project Euler Problem 3 - I can produce all factors of a number; but it
stops working when I go for the prime number

Also, large numbers murders it.
*/
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

int main(int nNumberofArgs, char* pszArgs[])
{
    int x = 1;
    int a = 2;
    long long limit = 13195LL;
    long long factor = 0LL;
    int prime = 0;

    for (;x <= limit; x++)
    {
      factor = limit % x;
      if (factor == 0)
      {
        cout << x
             << " is a factor of "
             << limit
             << "."
             << endl;
        
      }
    }
       
    //wait until user is ready before terminating program
    //to allow the user to see the program results
    system ("pause");
    return 0;
}    

Doing this, I get the following results:

Code: Select all

1
5
7
13
29
35
65
91
145
203
377
455
1015
1885
2639
13195

It's fine here because I see the sample primes. When I try to do the actual number of 600851475143, it just doesn't work. When I input that number in the limit, it runs factors until 716151937 then it runs the negatives of all the previous factors, which is obviously wrong.

Where am I messing up? I need this step to work out before I can start generating prime numbers.

Thanks

[TripleM]

x is an int - what is the largest possible value an int can be?