6,068
edits
Changes
Jump to navigation
Jump to search
Line 1:
Line 1: − A '''prime number''' is a number that is evenly divisible by no other number except for itself and 1. A number which is not prime is called a [[composite number]]. The classifications ''prime'' and ''composite'' apply to positive integers greater than 1, though there are related concepts in other fields of mathematics. Note that 1 is neither prime nor composite.+ − − The smallest prime numbers are 2, 3, 5, 7, 11, 13... . An exmple of a composite number is 6, which is evenly divisible by both 2 and 3. − − It is easy to prove that there are an infinite number of primes. If there were a finite number of primes, you could multiply them all together and add 1. The resulting number would show the existence of a new prime, since it would not be divisible by any smaller prime (it would always have a remainder of 1). − − To construct a table of prime numbers, you would use a method called the '''Sieve of Eratosthenes'''. Simply write down an ordered list of all counting numbers greater than 1. Beginning with 2*2 = 4, cross out every second number: − − :2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> 9 <s>10</s> 11 ... − − then beginning with 3*3 = 9 cross out every third number: − − :2 3 <s>4</s> 5 <s>6</s> 7 <s>8 9 10</s> 11 ... − − Beginning with 5*5 = 25, cross out every fifth number, then repeat for the primes 7, 11, 13, etc. The result will be a table of primes which is accurate up to ''n''-squared, where ''n'' is the largest number you sieved for. − − ==Primality testing== − To determine whether a number is prime, you can use the trial division method, provided the number you are testing is not too large. Let ''N'' be the number being tested and ''s'' be its square root. Divide ''N'' by each number in the prime table, beginning with 2. If there is no remainder, stop--N is composite. Otherwise, test again with the next largest prime in the table. If the next largest prime is greater than ''s'', stop--''N'' is prime. − − For larger values of ''N'', a method based on Fermat's theorem can be used, though it usually requires a computer. Start with the number 1, and double it ''N-1'' times. Divide this number by ''N'', keeping only the remainder. If the remainder is greater than 1, ''N'' is composite. Unfortunately, the converse is not true--if the remainder is 1, ''N'' is ''probably'' prime, but not necessarily. Algorithms which improve on this method exist, and primality testing is today an active subject of mathematical research. − [[category:mathematics]]
Redirecting to Prime number
#REDIRECT [[Prime number]]