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.
This is a discussion on Mathematical concept for prime numbers within the C Programming forums, part of the General Programming Boards category; Hello, I'm looking for a mathematical algorithm, that I can use as a guideline for a code I'm busy with. ...
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)The sqrt(n) limit is because you can't have a divisor larger than that.
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
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.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"