posted 6 years ago

I'm a newbie programmer and I've been solving Project Euler problems.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My problem is that if I put the following it does not give any result. In the previous code, it printed out all the prime factors and I put the last one as the answer as the maximum prime factor. I want to make a code that only gave the maximum, but if I used the following, there's no output at all. Where did I go wrong and what should I do?

Please help!Thank you in advance!

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My problem is that if I put the following it does not give any result. In the previous code, it printed out all the prime factors and I put the last one as the answer as the maximum prime factor. I want to make a code that only gave the maximum, but if I used the following, there's no output at all. Where did I go wrong and what should I do?

Please help!Thank you in advance!

posted 6 years ago

Perhaps you didn't wait long enough? It could take quite a while to figure out if 600 billion numbers are factors of that number, which is what you would be doing if it were prime.

By the way let me point out that the smallest non-trivial divisor of any number must be prime. You don't need to do that check.

By the way let me point out that the smallest non-trivial divisor of any number must be prime. You don't need to do that check.

posted 6 years ago

Don't start at 1.

`long div=600851475143L % 1`is always 0. Start at 2 instead, as that's the smallest prime number, not 1.SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

posted 6 years ago

It gives out the individual results very quickly, so can it be a problem with speed?

I am a bit confused with what you meant by smallest non trivial divisor of a number. Could you explain it a bit more?

Paul Clapham wrote:Perhaps you didn't wait long enough? It could take quite a while to figure out if 600 billion numbers are factors of that number, which is what you would be doing if it were prime.

By the way let me point out that the smallest non-trivial divisor of any number must be prime. You don't need to do that check.

It gives out the individual results very quickly, so can it be a problem with speed?

I am a bit confused with what you meant by smallest non trivial divisor of a number. Could you explain it a bit more?

Campbell Ritchie

Marshal

Posts: 56592

172

posted 6 years ago

The smallest trivial divisor is 1.

You want to start from 2 looking for divisors, so if you find it, 2 is the smallest non-trivial divisor. You keep dividing by 2 until it no longer divides exactly. Then you know 4 6 8 10 or any other even number cannot be a divisor. The next possible divisors are 3 and 5, which (like 2) are prime numbers. Again, if you find it divides by 3, and you keep dividing by 3 until it divides no longer, you want to look for the next prime numbers (5 7 and 11) because 6 (and 9) will not divide into it.

You want to start from 2 looking for divisors, so if you find it, 2 is the smallest non-trivial divisor. You keep dividing by 2 until it no longer divides exactly. Then you know 4 6 8 10 or any other even number cannot be a divisor. The next possible divisors are 3 and 5, which (like 2) are prime numbers. Again, if you find it divides by 3, and you keep dividing by 3 until it divides no longer, you want to look for the next prime numbers (5 7 and 11) because 6 (and 9) will not divide into it.

Campbell Ritchie

Marshal

Posts: 56592

172