import java.util.Scanner; |
Friday, September 21, 2012
Optimized Trial Division Prime Number Checking
Wikipedia definition of a prime number: "A prime number (or a prime) is a natural number greater than 1 that has no positive divisorsother than 1 and itself." On that page, if you scroll down a bit, you'll see "Testing Primality...". The following is a little 'Trial Division' method of determining if an entered int is a prime. It is obviously limited to small numbers (java int), and it is not as efficient as the 'deterministic' algorithms mentioned on that page (which are O(logi(n) [iterative logarithmic], better than the presented code's ~ O(n1/2)). It does, however, skip over all even and numbers divisible by 3 (other than 2 and 3, which are valid input).
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment