What is prime number? - Definition from WhatIs.com
Part of the Mathematics glossary:

A prime number is a whole number greater than 1, whose only two whole-number factors are 1 and itself.  The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.  

As we proceed in the set of natural numbers N = {1, 2, 3, ...}, the primes become less and less frequent in general.  However, there is no largest prime number.  For every prime number p, there exists a prime number p' such that p' is greater than p.  This was demonstrated in ancient times by the Greek mathematician Euclid.

Suppose n is a whole number, and we want to test it to see if it is prime.   First, we take the square root (or the 1/2 power) of n; then we round this number up to the next highest whole number.  Call the result m.  We must find all of the following quotients:

qm = n / m
q(m-1) = n / (m-1)
q(m-2) = n / (m-2)
q(m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2

The number n is prime if and only if none of the q's, as derived above, are whole numbers.

A computer can be used to test extremely large numbers to see if they are prime.  But, because there is no limit to how large a natural number can be, there is always a point where testing in this manner becomes too great a task even for the most powerful supercomputers.  Various algorithms have been formulated in an attempt to generate ever-larger prime numbers.  These schemes all have limitations.

A Mersenne prime must be reducible to the form 2 n - 1, where n is a prime number. The first few known values of n that produce Mersenne primes are where n = 2, n = 3, n = 5, n = 7, n = 13, n = 17, n = 19, n = 31, n = 61, and n = 89.

A Fermat prime is a Fermat number that is also a prime number . A Fermat number n is of the form 2 m + 1, where m is the n th power of 2 (that is, m = 2 n , where n is an integer). 

This was last updated in June 2015
Posted by: Margaret Rouse

Related Terms


  • backpropagation algorithm

    - The backpropagation algorithm repeatedly processes data to improve the accuracy of predictions in machine learning and neural network applications. (SearchBusinessAnalytics.com)

  • extrapolation and interpolation

    - Extrapolation is an estimation of a value based on extending a known sequence of values or facts beyond the area that is certainly known. (WhatIs.com)

  • negative correlation

    - A negative correlation is a relationship between two variables such that as the value of one variable increases, the other decreases.  Correlation is expressed on a range from +1 to -1, known as th... (WhatIs.com)


  • Mathematics

    - Terms related to mathematics, including definitions about logic, algorithms and computations and mathematical terms used in computer science and business.

  • Internet applications

    - This WhatIs.com glossary contains terms related to Internet applications, including definitions about Software as a Service (SaaS) delivery models and words and phrases about web sites, e-commerce ...

Ask a Question. Find an Answer.Powered by ITKnowledgeExchange.com

Ask An IT Question

Get answers from your peers on your most technical challenges

Ask Question
  • program

  • Problem Printing 12 CPI from our AS/400 with our new printer OKI 3391 ML

    Strange.... is it only this type printer that won't print the 12 CPI ?? We print to many types of printers and font sizes. We just set up overides in our CL programs and have had no problems OVR...

  • Java Program

    Here are my comments: - In the first hint, you say the 4th Z corresponds to a very large M, but M is not defined in the problem description. - The fourth hint say that Z must be a subclass of R, a...

Tech TalkComment



    Contribute to the conversation

    All fields are required. Comments will appear at the bottom of the article.