Project Euler Forum

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.

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

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 !

Merged posts with the Problem 003 thread.

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!

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.

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

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)

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.

Are you using 32 or 64 bit numbers?

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.

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!

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.

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?

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

You just need the largest prime factor

Hi,

Shame on me

It works with the largest one.

Thx for the quick help.

Have a nice day, Charles

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?

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.

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?