Thread: Mathematical concept for prime numbers

  1. #1
    Registered User
    Join Date
    Feb 2010
    Posts
    33

    Mathematical concept for prime numbers

    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.

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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)
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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.

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Large Numbers
    By mcdant01 in forum C++ Programming
    Replies: 9
    Last Post: 10-07-2009, 12:16 AM
  2. Help with outputting a list of squared numbers
    By dnguyen1022 in forum C++ Programming
    Replies: 28
    Last Post: 01-19-2009, 09:06 AM
  3. Matching numbers
    By kirksson in forum C Programming
    Replies: 7
    Last Post: 07-23-2008, 01:51 PM
  4. Question about random numbers
    By Kempelen in forum C Programming
    Replies: 2
    Last Post: 07-02-2008, 06:28 AM
  5. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 11:15 AM