Project Euler Forum

Hi,

I am stuck at problem 3 - C doesn't want to work with number 600 851 475 143 ... It's too big even for long long int.
Maybe I could bypass it with header files like BigInt etc., but I think that that huge number is there for a reason.
I think that I am supposed to think another way to calculate that largest prime factor - although for "small" numbers my program works just fine.
But in that case I am completely lost - I can't figure it out...

Could anybody give me an advice?
Thanks!

The biggest number that a long long int can hold is 9 223 372 036 854 775 807, which looks big enough to me

TripleM wrote:The biggest number that a long long int can hold is 9 223 372 036 854 775 807, which looks big enough to me

Oh, I didn't know that. I just tried unsigned long int, which is yet not sufficient for some problems.

uws8505 wrote:I just tried unsigned long int, which is yet not sufficient for some problems.

In many C or C++ implementations an int has the same size as a long. If they are equal size, then long long is usually bigger, but there is no guarantee. Try printing sizeof(int), sizeof(long), and sizeof(long long) to see how many bytes they use on your system.

If you declare
long long n = 1234567890123;
your compiler should tell you something like "integer constant is too large for "long" type", you must declare
long long n = 1234567890123LL;
or use lowercase for the specification of the type (would be ull for unsigned long long) to suppress the warning. However, it might even work without the type suffix.

2 Daniel:

I tried that "long long n = 1234567890123LL;" - there was a change (it compiled), but after I start it, it counts and counts and counts - or maybe not, I don't know - it didn't finish yet ... One-minute rule not fullfiled here... I must try different algorithm

But thanks anyway!

EDIT: Oh, great! Wikipedia says:

By the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. Given an algorithm for integer factorization, one can factor any integer down to its constituent primes by repeated application of this algorithm. For very large numbers, no efficient algorithm is known. For smaller numbers, however, there are a variety of different algorithms that can be applied.

I guess 600851475143 is pretty "very large number", huh?

Did you change it back to 600851475143LL ?

The largest primefactor of 1234567890123 is 116216501 and that's rather high.
The largest primefactor of 600851475143 isn't that high.

BTW the size of the number is not exactly what makes factoring difficult or easy. It's the size of the primefactors that is relevant.

MaJJ wrote:I guess 600851475143 is pretty "very large number", huh?

Not really. It's high if you do it by hand, but for a computer less than 10 years old, it's a piece of cake.
"Very large" means roughly more than 100 digits.

Then I am using wrong algorithm ...

My program is this: ... just put it into notepad or something

MaJJ wrote:Then I am using wrong algorithm ...

The algorithm is correct (though there's a small implementation error), but unnecessarily slow. One small change will let it finish in reasonable time. I suggest you follow it with pencil and paper for a small number to see where you can improve it.

MaJJ wrote:Then I am using wrong algorithm ...

My program is this:

Code: Select all

    long long number = 600851475143LL;
    int assist = number;    

Why are you using different types?

Wooohohooow, THAT was something fast
Thanks a lot!

... I guess I should edit my previous post and delete that "spoiler", so other people can have fun too

I seem to have run into a problem with problem 3.

I only know how to program in php (for now) since my high school doesn't offer computer science and I kind of picked up php in my spare time instead of C or something else.

In any case, I've developed a script which will get all the prime numbers from 1 to X and then it sees which ones are factors of X.

Script is flawless as long as I input a smallish number. Anything too big won't work....the page will load for a few minutes and eventually just come up with a blank page, no error or anything. I've set max execution time in php.ini to unlimited so that can't be it.

Any ideas?

I can't even get it to spit out the answer for the demo number in the problem (13195). It obviously can't do 600851475143.

It seems to be able to do numbers in the thousands, but ten-thousand doesn't work which explains why 13k won't either I guess.

Am I approaching it the wrong way?

Your browser is probably what is doing the timing out.

If you know some PHP, then you probably won't find it too hard to pick up another scripting language, like Perl, Python or Ruby. (Since you don't have much to unlearn you could take the opportunity to go farther afield to a language like Lisp or Haskell instead.) If you want to use a web language, even JavaScript would give you the opportunity to get meaningful feedback from your script as it is running.

Alternately you could pick up some advice from http://www.devshed.com/c/a/PHP/Logging-With-PHP/1/ about how to write a log file, and write a log as PHP is running. That will help you debug your script. For instance log when it finds each prime and you can see how much time you are spending trying to generate primes.

As for your solution, there are many potential improvements that can be made. First your way of generating primes sounds slow. At a guess, you are checking each possible prime by trying to divide by every number less than it. Reading an article like http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes may give you ideas on how to do that much more quickly. (Having a fairly efficient way to generate a list of primes will help you a lot on many later problems.) Secondly you are generating far more primes than you need. Even an efficient prime sieve will not generate all of the primes up to 600851475143 in any reasonable time, and even if it could, storing over 22 billion primes would take up a lot of memory.

In general a good way to think about the viability your proposed solution is in terms of the number of operations you think you'll need. You have 1 minute. You have a machine that probably executes millions operations per second in a fairly slow interpreted language. So if you can think of an algorithm that probably requires a few hundred million operations, then it may be fast enough. If it probably requires a few billion operations, then you need a better algorithm. As you've just discovered, having one loop in another loop takes the size of the inner loop times the size of the outer loop instructions, which can quickly become a very large number. Doing project Euler problems should help you develop your intuition on this.

A random hint. Can you find an approach that doesn't require you to generate the list of primes at all?

Thanks!

I'll try and 'port' that prime algorithm into php and see what I can come up with.

rafael wrote:Thanks!

I'll try and 'port' that prime algorithm into php and see what I can come up with.

While porting would be good, if you try to generate all of the primes up to 600851475143, you will still have huge problems.

Ahhh this is do difficult D:

Oh well, that's half the fun I suppose

rafael wrote:Ahhh this is do difficult D:

Oh well, that's half the fun I suppose

And more than half of the benefit. Particularly since you're young, some practice solving this type of problem now will turn into an ability to think mathematically for the rest of your life. And I can't overemphasize how useful that can be. (And fun.)

I think I'm dropping PHP.

Any thoughts on python?

Fantastic language, can't say enough goodness about it. Not quite as fast as C/C++/C#, but given that most all fun programming concepts can be done with the language (generators, co-routines, etc) I love playing around with it. Give it a shot, it's one of the easiest languages I've had to learn.