1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Determine prime number

  1. Aug 10, 2006 #1
    can smby give me a simple example algorithm to determine whether the number is prime or not such as using while loop, if.....then......else or others which is simple

    thanx
     
  2. jcsd
  3. Aug 10, 2006 #2

    berkeman

    User Avatar

    Staff: Mentor

  4. Aug 10, 2006 #3
    but I'm looking for a simple example about prime number determination [algorithm] for programming language only using if.....then... or while loop or repeat loops..... that describe the steps of calculation
     
  5. Aug 10, 2006 #4

    berkeman

    User Avatar

    Staff: Mentor

    How many of those google hits did you actually look through?
     
  6. Aug 10, 2006 #5
    A simple example I can think of is go through every integer between 1 and the prime number you want to test and check to see if it is a divisor.
     
  7. Aug 11, 2006 #6
    you only need to go up to a third of the number. This is because if it is even then you know it is not prime, unless it is two. odd numbers are not divisble by 2, so the next divisor would be 3.
     
  8. Aug 11, 2006 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    It's enough to go up to the square root of the number, much more efficient than having to check up to a third (still not at all fast though).
     
  9. Aug 11, 2006 #8

    rbj

    User Avatar

    and you only need to test (up to the [itex]\sqrt{N}[/itex] ) the odd numbers that are not known multiples of other prime numbers (like multiples of 3, 5, 7, 11, 13, etc). if your programming language has a remainder operator (like the "%" operator in C and C++), you can use that to test a candidate factor to see if it divides evenly into N. but if you don't, you have to divide, use the floor() or int() operator to get the integer part of the quotient, subtract the integer part from the quotient and, if that result is zero, it divides evenly.

    if all candidate factors fail to divide evenly into N, then N is prime. if any one candidate factor divides evenly into N, it is not prime.
     
  10. Aug 11, 2006 #9
    okok........thanx
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?