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.
Right 98% of the time, and don't care about the other 3%.
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"