Posted: Sat Sep 29, 2007 3:08 pm
I am aware of this, however, as far as i know there is no instruction which calculates sqrt. There is allso other ways of optimizing, but tht is not really the point. This code is just and example of the basic algorithm (or what you call it)Combuster wrote:You can eliminate a lot of components:
consider all cases where a = b * c (i.e., not prime) and make b >= c
now, the largest value c can attain is b, i.e a = c * c -> c = sqrt(a)
you will only need to check the numbers up to and including sqrt(a) to determine primehood.
Anyway, i was thinking, that calculation primes in this fasion will result in hitting a limit at some point or another, depentent on how many bits the cpu operates with. Considering this it might be better just to make as sieve, eg. make a list og numer from n 2 to n, then exclude all the the number divisible by 2, 3, 5 etc.
Also, if using the forst methode im considering if it would be a good idea making a list of squares, it qould take up some more memory, but it could drasticly improve the performance...
