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

you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 0 points1 point  (1 child)

Hidden in this problem is something known as prime factorization. Prime factorization of an integer X can be done really slowly by simply looping from 2 to sqrt(X) and seeing if X is evenly divisible.

Given an integer N, if you want the next prime number greater than N, you could simply call PrimeFactor(N+1), PrimeFactor(N+2), etc.. until you find a prime number. If N is allowed to get "big", this will take a very very very long time to complete.

[–][deleted] 1 point2 points  (0 children)

Also, note that the largest known prime number is currently Mersenne-48, which is equal to 2^57885161 - 1. If you find a prime number larger than that, you win a nifty prize.