# Homework Help: Determine prime number

1. Aug 10, 2006

### teng125

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. Aug 10, 2006

### Staff: Mentor

3. Aug 10, 2006

### teng125

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

4. Aug 10, 2006

### Staff: Mentor

How many of those google hits did you actually look through?

5. Aug 10, 2006

### buddyholly9999

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.

6. Aug 11, 2006

### a_ramage_1989

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.

7. Aug 11, 2006

### shmoe

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).

8. Aug 11, 2006

### rbj

and you only need to test (up to the $\sqrt{N}$ ) 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.

9. Aug 11, 2006

### teng125

okok........thanx