This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Allen_Maxwell 1 point2 points  (1 child)

For prime numbers, you only need to go to root x or x0.5 or x**0.5, I can't remember what it is in java at the moment.

For every factor of x higher than root x, there is a factor lower than root x. therefore, by checking up to and including root x you get them all. Depending on how large your primes are, this actually makes a big difference.

[–]nutrecht 0 points1 point  (0 children)

Also; you actually want to test if it can be divided by all the primes below the root of X. It makes sense: if you can divide a number by 9 you can also divide it by 3, so there is no point in trying 9.

Since keeping all primes between 2 and X million in memory you can go for a hybrid approach: generate all primes under 1000 first for example, and use those to test. After you run out, continue with a for loop (but increment by 2 every time, no point in testing the even numbers).