[ghostrider_]

well the project is find the largest prime factor of a number (any number between 1 and 100.000.000) and compare it with a number B(lets say 1024).
i am about to build a list of primes up to 1024.. then i 've got two ideas.. the one -brute force divisibility testings..start from the firti prime and proceed to the next one etc..

but the other one- which if it is true may be fastest is: start from the nearest prime number to sqrt(n), see if it divides the number.. if not go to the previous one.. the firs to find is the largest.. do you think its ok??
my problem in the second idea is what will happen if the sqrt(n) is bigger than 1024.. how can i check if there is at least one prime factor between 1024 and sqrt(n)..??

This post has been edited by ghostrider_: 20 April 2010 - 03:12 PM

[mojo666]

Build the list of primes up to 10000. sqrt(n) will never be larger than this because you are guarenteed the largest input is 10000^2.

[ghostrider_]

mojo666, on 20 April 2010 - 02:22 PM, said:

Build the list of primes up to 10000. sqrt(n) will never be larger than this because you are guarenteed the largest input is 10000^2.

yes but i think this will make my programm uneficient.. i am wondering if anyone can think of a trick to avoid that, something that i miss.. thanks anyway.. in addition, the number i gave you (100.000.000 is one of the testacase that the project is going to be tested-its not stable number)

This post has been edited by ghostrider_: 20 April 2010 - 03:37 PM