Problem 003

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

Problem 003

Post by MaJJ »

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!
Image
Image

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 3 - Huge number

Post by TripleM »

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

User avatar
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 3:13 pm
Location: South Korea

Re: Problem 3 - Huge number

Post by uws8505 »

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.
Math and Programming are complements

User avatar
jaap
Posts: 551
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 3 - Huge number

Post by jaap »

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.

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 3 - Huge number

Post by daniel.is.fischer »

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.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

Re: Problem 3 - Huge number

Post by MaJJ »

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? :D
Image
Image

User avatar
hk
Administrator
Posts: 10889
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 3 - Huge number

Post by hk »

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.
Image

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 3 - Huge number

Post by daniel.is.fischer »

MaJJ wrote:I guess 600851475143 is pretty "very large number", huh? :D
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.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

Re: Problem 3 - Huge number

Post by MaJJ »

Then I am using wrong algorithm ...

My program is this:

Code: Select all

EDIT: figure it yourself :)
... just put it into notepad or something :)
Last edited by MaJJ on Tue Oct 14, 2008 7:48 pm, edited 1 time in total.
Image
Image

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 3 - Huge number

Post by daniel.is.fischer »

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.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

User avatar
Georg
Posts: 157
Joined: Mon Jan 21, 2008 7:00 am
Location: Mannheim, Germany
Contact:

Re: Problem 3 - Huge number

Post by Georg »

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?

MaJJ
Posts: 49
Joined: Tue Oct 14, 2008 12:14 am

Re: Problem 3 - Huge number

Post by MaJJ »

Wooohohooow, THAT was something fast :D
Thanks a lot!

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

rafael
Posts: 4
Joined: Fri Oct 31, 2008 10:18 pm

Problem 3

Post by rafael »

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?

btilly
Posts: 44
Joined: Fri Sep 26, 2008 7:45 am

Re: Problem 3 :(

Post by btilly »

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?

rafael
Posts: 4
Joined: Fri Oct 31, 2008 10:18 pm

Re: Problem 3 :(

Post by rafael »

Thanks!

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

btilly
Posts: 44
Joined: Fri Sep 26, 2008 7:45 am

Re: Problem 3 :(

Post by btilly »

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.

rafael
Posts: 4
Joined: Fri Oct 31, 2008 10:18 pm

Re: Problem 3 :(

Post by rafael »

Ahhh this is do difficult D:

Oh well, that's half the fun I suppose :P

btilly
Posts: 44
Joined: Fri Sep 26, 2008 7:45 am

Re: Problem 3 :(

Post by btilly »

rafael wrote:Ahhh this is do difficult D:

Oh well, that's half the fun I suppose :P
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.)

rafael
Posts: 4
Joined: Fri Oct 31, 2008 10:18 pm

Re: Problem 3 :(

Post by rafael »

I think I'm dropping PHP.

Any thoughts on python?

quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Re: Problem 3 :(

Post by quilan »

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.
ex ~100%'er... until the gf came along.
Image

Post Reply