Problem 003

oshillwm · Post by **oshillwm** » Tue Sep 20, 2011 11:30 pm

With the problem asking for the largest prime in some huge ridiculous number, i have a prime number finding program which can quickly solve for all primes up to said number, but somewhere i have messed up i guess in returning the set of prime factors. I am pretty new and am using Pythonv2.7.2 (currently using it in cs141 for college) if anyone can help please pm me since i am unsure as to how strict the no codes rule is.

thedoctar · Post by **thedoctar** » Wed Sep 21, 2011 7:23 am

Post your problem in the appropriate topic, ie Problem xxx. Please read this post :
Comments, questions and clarifications about PE problems.
Particularly:

harryh wrote:If there is no previous topic for the specific problem you are trying to solve, you may start a new topic, giving as subject Problem xxx. Please do not use in the Subject-field expressions like "Clarification needed", "problem with the wording", "Correct answer not accepted" etc

Belgarion120 · Post by **Belgarion120** » Wed Sep 21, 2011 3:18 pm

I spent the whole day on this one... just because I forgot that using % with very large numbers in PHP is pretty stupid.
I don't think I'm spoiling anything by saying this : don't use % but fmod() when you want the modulus on large numbers in PHP !

rayfil · Post by **rayfil** » Thu Sep 22, 2011 1:18 am

Merged posts with the Problem 003 thread.

PoetAC · Post by **PoetAC** » Fri Sep 23, 2011 1:19 am

Can someone please help me with my code. I know how I want to solve the problem, though it may not be the most efficient way. My code is not working how I expect it to work.

It is a very simple C++.

If anyone is willing, please pm me and I will send you the code.
Thanks!

ayberkt · Post by **ayberkt** » Sat Nov 03, 2012 8:36 pm

Hi everyone,

I have recently found out about project euler and started with the challenges. For the problem #3 I implemented a sieve of erastothenes method but this takes too much time that I can't get the required number calculated.

Am I missing a detail, is it possible to do it with the sieve method? Or should I just try to implement a more efficient algorithm.

I'd really appreciate some help I can't move on to the other problems without having completed number 3.

I'm using python.

Thanks.

thundre · Post by **thundre** » Sat Nov 03, 2012 8:53 pm

ayberkt wrote:For the problem #3 I implemented a sieve of erastothenes method but this takes too much time that I can't get the required number calculated.

Am I missing a detail, is it possible to do it with the sieve method? Or should I just try to implement a more efficient algorithm.

For finding all primes up to a certain limit, the sieve of Eratosthenes is one of the most efficient algorithms.

But there is a better way to solve this problem than doing trial division on all primes from 2 to 600851475143. You might get an idea from reading this:
http://en.wikipedia.org/wiki/Fundamenta ... arithmetic

billyjayan · Post by **billyjayan** » Tue Jul 23, 2013 5:37 pm

I wrote a code in c which checks whether a number is prime and then checks if it is a factor, the loop checks for all numbers from 2 to the squareroot of the number. the program appears to be running for small numbers and the number given in the example, but does not work for the question(obvious;but I didn't find any other way). Guide me through this, subtle hint will do( tell me what am I doing wrong)

TheEvil · Post by **TheEvil** » Tue Jul 23, 2013 6:08 pm

Since you are looking for prime factors, why don't you try to factorize it, instead of checking every prime number. I think this hint should be enough.

pieppiep · Post by **pieppiep** » Tue Jul 23, 2013 6:17 pm

Are you using 32 or 64 bit numbers?

TheEvil · Post by **TheEvil** » Tue Jul 23, 2013 7:52 pm

When I did it I used 32 bit integers. It was a lot more complicated than with 64 bit integers. That is trivial if you have the necessary idea.

billyjayan · Post by **billyjayan** » Wed Jul 24, 2013 6:51 pm

TheEvil wrote:Since you are looking for prime factors, why don't you try to factorize it, instead of checking every prime number. I think this hint should be enough.

you have to find the factors, but still would have to check whether they are prime, more or less the same thing(I tried both ways) the code takes forever to complete!

TheEvil · Post by **TheEvil** » Thu Jul 25, 2013 6:11 am

If you do it properly, you have to know only that 3 is the smallest odd prime number. You don't have to know any other prime numbers. Maybe it doesn't help you, but it's the key idea.

extremeblueness · Post by **extremeblueness** » Wed Aug 14, 2013 12:44 am

jaap wrote:
rineez wrote:Anybody done this in java?
I'm working with java and i am confused which data type to use to hold this number 600851475143.
My compiler is showing error "integer number too large: 600851475143" !
But I thought this number is within the range of long.
It does fit in a long, but it tries to interpret the literal number 600851475143 as an integer during compilation, and this fails. You must put an L at the end of the number to indicate that it is to be interpreted as a long integer.
long m = 600851475143L;

THANK YOU THANK YOU THANK YOU THANK YOU THANK YOU THANK YOU THANK YOU THANK YOU THANK YOU THANK YOU, and did I say Thank You?

charles.walker.37 · Post by **charles.walker.37** » Sat Apr 19, 2014 9:10 am

Hello,

I think I found the correct algo to solve it but my answers are rejected. Just to be sure that my response was correct I found an online site to determine the prime factor of big number ( http://calculis.net/grand-nombre-premier ) which give me the same result that my algo....

I tried to answer the number with and without coma between them and also with the same formating than the exemple : "The prime factors of 13195 are 5, 7, 13 and 29." and thus enter the response W, X, Y and Z but it was still failling....

How should be the answer formated if the response include 4 number W, X, Y, Z (with W < X < Y < Z) ?

Thanks, Charles

pieppiep · Post by **pieppiep** » Sat Apr 19, 2014 9:14 am

You just need the largest prime factor

charles.walker.37 · Post by **charles.walker.37** » Sat Apr 19, 2014 9:34 am

Hi,

Shame on me

It works with the largest one.

Thx for the quick help.

Have a nice day, Charles

Zahand · Post by **Zahand** » Sun May 25, 2014 12:51 am

Hello.

I have a problem with problem 003.

It took me a while (still new to programming) but I got an answer. I tried it but the page just reload, and doesn't say anything.
I am sure my answer is correct, because I checked it with wolframalpha and I got the same answer. Is there a bug with problem 3?

Yacob · Post by **Yacob** » Fri Aug 01, 2014 10:49 pm

TheEvil wrote:If you do it properly, you have to know only that 3 is the smallest odd prime number. You don't have to know any other prime numbers. Maybe it doesn't help you, but it's the key idea.

This all the way. I factorized the number, and I got a quick correct answer. The key is being able to successively break that number down.

Aidan_Murphy · Post by **Aidan_Murphy** » Sat Aug 16, 2014 12:06 am

I have a working solution for Problem 003 written in Matlab (GNUOctave, really), but the runtime is atrocious. Can I PM anyone my code to get some suggestions on where I might improve it?

Project Euler Forum

Problem 003

Problem with a return on prime factors program

Re: Problem with a return on prime factors program

Re: Problem 003

Re: Problem with a return on prime factors program

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Re: Problem 003

Problem 003

Re: Problem 003

Re: Problem 003