Whether or Not a Number is Prime or Composite


Prime Number Calculator

Enter a positive integer with at most 15 digits below:

 

In mathematics, a positive integer is considered prime if its only two factors are 1 and itself. A positive integer is considered composite if it has more than two factors. (0 and 1 are neither prime nor composite.) Knowing whether or not a number is prime or composite is a useful tool in pure mathematics, and there are many real-world applications of prime numbers as well.

For example, if you can determine whether the numerator or denominator of a fraction is prime, then you know that the fraction cannot be reduced. In cryptography, composite numbers that are the products of very large prime numbers can be used to encrypt information.

The methods described here will teach you how to tell if an integer is prime or composite. For a quicker reference, use the handy prime number checker on the left.


First, look at the last digit of the number, the ones digit. If the ones digit is a 2, 4, 5, 6, 8, or 0, then the number is composite. (The only exceptions to this rule are the numbers 2 and 5 themselves, which are prime.) This rule works because any number that ends in 2, 4, 6, 8, or 0 is even, i.e., divisible by 2. And any number that ends in 5 or 0 is divisible by 5.

What if the number ends in 1, 3, 7, or 9? If it is less than 300, you can check if it is in this list of prime numbers that are less than 300:

3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293.

Any number that is less than 300 and not in this list must be composite.

Of course, there are infinitely many prime numbers and infinitely many composite numbers, so what should you do if you need to check a number that is larger than 300? One algorithm for checking whether or not a number is prime is to divide it by smaller prime numbers.

For example, suppose we want to know if 493 is prime. We can start by dividing it by 3, 7, 11, 13... When we compute 493/17, we get 29. So 493 is composite since its factors are 1, 17, 29, and 493.

When applying this method, you only need to divide by primes that are less than the square root of the number.

For example, suppose we want to know whether or not 1249 is a prime integer. Since sqrt(1249) = 35.34, we only need to check all the primes up to 35. That is, we only need to check if 3, 7, 11, 13, 17, 19, 23, 29, and 31 will divide evenly into 1249. (We do not need to check 2 and 5 since 1249 is neither even nor a multiple of 5.)

It turns out that none of 3, 7, 11, 13, 17, 19, 23, 29, or 31 will divide evenly into 1249. Thus, 1249 is a prime number.

There are computer programs and special calculators that can do these computations more quickly for extremely large integers. As you go up in the integers, prime numbers become more and more scarce. However, mathematicians have been able to identify prime numbers with over 12 million digits using more advanced techniques. If you want to test smaller numbers with up to 15 digits, use the quick calculator above. (Must have JavaScript enabled on your web browser.)



© Had2Know 2010