Hello,
I'm looking for a mathematical algorithm, that I can use as a guideline for a code I'm busy with.
I'm looking for a very basic mathematical algorithm which will determine whether a certain value is prime or not.
Printable View
Hello,
I'm looking for a mathematical algorithm, that I can use as a guideline for a code I'm busy with.
I'm looking for a very basic mathematical algorithm which will determine whether a certain value is prime or not.
Ok in order to determine whether a number n is prime or not you do the following:
- iterate from 2 to the closest integer of sqrt(n).
- if iterator divides n, then return not prime.
- return prime.
The reason you iterate from 2 not 1, is that 1 obviously divides any number including prime numbers. The sqrt(n) limit is because you can't have a divisor larger than that.
Actually you can, but you would have found it by that time: e.g 21 = 3 * 7 and 7 > sqrt(21)Quote:
The sqrt(n) limit is because you can't have a divisor larger than that.
Yes I stand corrected. What I meant was that if you cannot find one by sqrt(n) then the number is prime, because if it had a divisor greater than that then it would automatically have one (the quotient) smaller.
Thanks for pointing this out.
A more efficient way unless you're working only with small primes, albeit one that takes a little more work to code up, is the Sieve of Eratosphenes. Plenty of information on that one available via google.
Spelling error there on Sieve of Eratosthenes
The best technique to use all depends on how large this value might be.