# project euler

harish thiru

Ranch Hand

Posts: 32

posted 7 years ago

the question is project euler 3 one

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

What is the largest prime factor of the number 600851475143 ?

this gives answer 1471 second greatest

if i try i<=N it gives correct answer

Actually Jesper Young wrote somewhere this -- instead of testing all numbers between 2 and N, you only need to test all primes between 2 and the square root of N.

also i read from somewhere this

A prime number has only two distinct factors, 1 and itself, clearly the number itself is greater than the square root of itself.

Given n and a (which is a factor of n), then n / a is also a factor of n.

For example if n = 777 and a = 37, then 777 / 37 = 21 is also a factor of 777 as 777 / 21 = 37.

Suppose we have a factor b which is greater than the square root of n:

b > sqrt(n)

1 / b < 1 / sqrt(n) // inverse

n / b < n / sqrt(n) // multiply by n

n / b < sqrt(n) // cancel n1 / n0.5 = n0.5 = sqrt(n)

This shows that if we have some factor b greater than the square root of n then there must exist factors less than the square root of n also, therefore if we do NOT have any factors less than the square root of n then by contradiction we CANNOT have an factors greater than than the square root of n.

can anyone tell where i have gone wrong

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

What is the largest prime factor of the number 600851475143 ?

this gives answer 1471 second greatest

if i try i<=N it gives correct answer

Actually Jesper Young wrote somewhere this -- instead of testing all numbers between 2 and N, you only need to test all primes between 2 and the square root of N.

also i read from somewhere this

A prime number has only two distinct factors, 1 and itself, clearly the number itself is greater than the square root of itself.

Given n and a (which is a factor of n), then n / a is also a factor of n.

For example if n = 777 and a = 37, then 777 / 37 = 21 is also a factor of 777 as 777 / 21 = 37.

Suppose we have a factor b which is greater than the square root of n:

b > sqrt(n)

1 / b < 1 / sqrt(n) // inverse

n / b < n / sqrt(n) // multiply by n

n / b < sqrt(n) // cancel n1 / n0.5 = n0.5 = sqrt(n)

This shows that if we have some factor b greater than the square root of n then there must exist factors less than the square root of n also, therefore if we do NOT have any factors less than the square root of n then by contradiction we CANNOT have an factors greater than than the square root of n.

can anyone tell where i have gone wrong

Vlado Zajac

Ranch Hand

Posts: 245

harish thiru

Ranch Hand

Posts: 32

posted 7 years ago

Vlado Zajac i tried debugging before also

I get there is something wrong in the algorithm but i am thinking what Jesper Young was saying

i understood that there are prime factors greater than square root of n, but if you don't find one before square root of n then there won't be.

this means we have to use this only

probably i am missing something

I get there is something wrong in the algorithm but i am thinking what Jesper Young was saying

i understood that there are prime factors greater than square root of n, but if you don't find one before square root of n then there won't be.

this means we have to use this only

probably i am missing something

posted 7 years ago

There may be prime factors greater than the square root..for example take 28. The square root is somewhere between 5 and 6, and the factorization is 2*2*7 - 7 is clearly larger.

But here's what is probably your problem... if you are only checking the primes below the square root, you're checking 2, 3, and 5 - only one of which goes evenly into 28. HOWEVER, what you are missing is that 2 goes in TWICE... so when you divide 28/2, you get 14, which is not prime... but you're never gonna find (28/2)/2 (or 28/4) to get your 7.

I would say you have to check either all the primes less than the number, OR all the numbers below the square root... OR, after you check a prime that divides evenly, check to make sure it doesn't go in again and continue with the quotient each time... although I haven't proved that to myself yet.

But here's what is probably your problem... if you are only checking the primes below the square root, you're checking 2, 3, and 5 - only one of which goes evenly into 28. HOWEVER, what you are missing is that 2 goes in TWICE... so when you divide 28/2, you get 14, which is not prime... but you're never gonna find (28/2)/2 (or 28/4) to get your 7.

I would say you have to check either all the primes less than the number, OR all the numbers below the square root... OR, after you check a prime that divides evenly, check to make sure it doesn't go in again and continue with the quotient each time... although I haven't proved that to myself yet.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

harish thiru

Ranch Hand

Posts: 32

posted 7 years ago

fred rosenberger

i use this know

so i think for 28/2 then still i divide by 2 again so i get to 7 but then i do not consider it 7 as 7>sqrt(7)

to use that condition shouldn't i change the entire for loop code

sorry if i have misunderstood anything

originally posted by fred rosenberger

HOWEVER, what you are missing is that 2 goes in TWICE... so when you divide 28/2, you get 14, which is not prime... but you're never gonna find (28/2)/2 (or 28/4) to get your 7.

i use this know

so i think for 28/2 then still i divide by 2 again so i get to 7 but then i do not consider it 7 as 7>sqrt(7)

originally posted by fred rosenberger

OR, after you check a prime that divides evenly, check to make sure it doesn't go in again and continue with the quotient each time..

to use that condition shouldn't i change the entire for loop code

sorry if i have misunderstood anything

posted 7 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

I think the problem is that you have to test whatever you are left with to see if it's prime. take 66. it factors to 2*3*11. you're only testing up to 9. so you divide by 2, then by 3, and are left with 11. again, i THINK if you check to see if THAT is prime, you're done. If it's not prime, you need to find IT'S factors.

on a different tack... when I did this, I approached it differently. I wrote a method that would reduce an input. So, if you passed it 35, it would return 7. if you passed it 105, it would return 21. if the passed value was not reducible, it was prime.

If you always try and find the smallest factor first, when you're done, you're left with the largest prime factor of the original.

on a different tack... when I did this, I approached it differently. I wrote a method that would reduce an input. So, if you passed it 35, it would return 7. if you passed it 105, it would return 21. if the passed value was not reducible, it was prime.

If you always try and find the smallest factor first, when you're done, you're left with the largest prime factor of the original.

harish thiru

Ranch Hand

Posts: 32

posted 7 years ago

I don't get this, this is not true always know for example 68 has smallest prime factor has 2 then how are we left with the largest prime factor, unless you mean we start with lowest prime factors then increment and finally the last prime left which after all division is the largest prime factor.

which means i could have done this

there is no need of any if condition like

could you please post your code

originally posted by fred rosenberger

If you always try and find the smallest factor first, when you're done, you're left with the largest prime factor of the original.

I don't get this, this is not true always know for example 68 has smallest prime factor has 2 then how are we left with the largest prime factor, unless you mean we start with lowest prime factors then increment and finally the last prime left which after all division is the largest prime factor.

which means i could have done this

there is no need of any if condition like

could you please post your code

posted 7 years ago

You algorithm is correct - and every thing Jesper Young wrote about prime numbers is correct to!

You end up with a wrong answer for a classic but hard to spot error in your implementation.

The relevant lines ...

for (long i = 2 ; i <= Math.sqrt(

.

.

.

Hope that marks out the mistake clearly for you?

If you are still unclear - here is my next suggestion,

Add the following SOP just below where N = N/i;

P.S - I just started on project Euler too. Coincidence - http://java-twisters.blogspot.com/2009/06/puzzle-33-prime-number-optimization.html!

Yippy - This was my 200th post!!

You end up with a wrong answer for a classic but hard to spot error in your implementation.

The relevant lines ...

for (long i = 2 ; i <= Math.sqrt(

**N**); i++).

.

.

**N = N/i;**Hope that marks out the mistake clearly for you?

If you are still unclear - here is my next suggestion,

Add the following SOP just below where N = N/i;

P.S - I just started on project Euler too. Coincidence - http://java-twisters.blogspot.com/2009/06/puzzle-33-prime-number-optimization.html!

Yippy - This was my 200th post!!

Cheers - Sam.

Twisters - The new age Java Quiz || My Blog

posted 7 years ago

Sorry. My Bad. What I said above is incorrect.

The truth is we ended up mixing an algorithm that was for a different purpose with the one you use here.

The algorithm with the less than SQRT(N) is for "Determining if a Number is Prime or not" The logic it work on is pretty simple - if a Number has no factor less than or equal to its sqrt it must be prime."

However this does not mean that a number cannot have one or more prime factors greater than its Sqrt when it is not prime.

So for example, 66 - who sqrt is 9 (between 8 and 9, taking the higher value) has a factor of 2,3, and 11.

In this particular example your algorithm would work since the actual largest prime factor of the number is 6857 which is less the the SQRT of the number 600851475143L. This might not be generally true.

The truth is we ended up mixing an algorithm that was for a different purpose with the one you use here.

The algorithm with the less than SQRT(N) is for "Determining if a Number is Prime or not" The logic it work on is pretty simple - if a Number has no factor less than or equal to its sqrt it must be prime."

However this does not mean that a number cannot have one or more prime factors greater than its Sqrt when it is not prime.

So for example, 66 - who sqrt is 9 (between 8 and 9, taking the higher value) has a factor of 2,3, and 11.

In this particular example your algorithm would work since the actual largest prime factor of the number is 6857 which is less the the SQRT of the number 600851475143L. This might not be generally true.

Cheers - Sam.

Twisters - The new age Java Quiz || My Blog

Vlado Zajac

Ranch Hand

Posts: 245

harish thiru

Ranch Hand

Posts: 32

Brandon Bernie

Greenhorn

Posts: 9

harish thiru

Ranch Hand

Posts: 32

posted 7 years ago

Yeah even for even numbers i think we should first completely divide by 2, then we could increment by 2, lot of iterations saved.

When i posted solution i found out from project euler overview that

every number n can at most have one prime factor greater than sqrt(N) . If we,

after dividing out some prime factor, calculate the square root of the remaining number we

can use that square root as upper limit for factor. If factor exceeds this square root

we know the remaining number is prime.

This is what anyway you guys were telling me

When i posted solution i found out from project euler overview that

every number n can at most have one prime factor greater than sqrt(N) . If we,

after dividing out some prime factor, calculate the square root of the remaining number we

can use that square root as upper limit for factor. If factor exceeds this square root

we know the remaining number is prime.

This is what anyway you guys were telling me