How do you know if a number is composite or prime number?

Answer 1

The Sieve of Eratosthenes can be used for most of the lower primes; for how to use it, see the related links. For larger primes, i.e. those with more than 3 digits, it is quicker to use a simple algorithm.

1. Find the square root of the number you wish to determine and round upwards; this is your higher bound. The square root can often be estimated by rounding to the nearest 100 or 1000, as shown below. This does not affect the results, and may or may not cause redundancy in the division step.
2. List all prime numbers up to and including this bound. If you do not have all of the primes up to this point, then either continue the sieve until you do, or find some other primes using those already found and another number by this method. The primes from 1 to 500 are listed in a related question.
3. Divide the number by each of these primes in turn: a) if one of the primes can divide the number with no remainder, it is composite, b) if none of the primes divide it without remainder, it is also prime.

For example, deterimining whether 997 is composite or prime by this method;

• 997 is almost 1000, so the square root of 1000 (31.62) rounded upward will do for the purpose.
• The primes up until 32 are easily found by the sieve, if this has not been done already. They are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 and 31.
• Dividing 997 by each of these, we find that none of them divide exactly. Thus 997 is a prime.

Another example, using 5893;

• 5893 is almost 6000; the square root of this rounded upward is 78.
• The prime numbers we know to this point are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 and 31. Using the sieve again, we can find that the next primes are 37, 41, 43, 47, 53, 59, 61, 67, 71 and 73.
• Dividing 5893 by each, we find that just 71 divides 5893 exactly, into 83. These are actually the only factors besides 1 and itself as 83 is also prime. Thus 5893 is a composite.

Answer 2

A Prime number has only 2 factors which are 1 and itself. Composite numbers are everything else except 1 and 0. 1 and 0 are neither prime, nor composite.