il

R T
Panat o0 M)

==
%
=
4
=
: -
&
=
e
o
é

FRTETRTE Ihes SIVRGRITIE S0 SO LETENEEETAD 100 B

15*3*”»:.nlnmilm“nvmu’,‘wunnrmd.‘;,:“W“v

 

LI LTI ATE TRy

5

‘Primes and Factors’

A prime number is one which has no factors other than itself
and unity. Mathematicians have been searching for centuries
to discover a simple test which would enable them, without
any great labour, to declare whether or not any specific num-
ber is a prime. Many methods have been suggested and
proved, but they do not materially shorten the work of testing
for primality.

For small numbers the tests of divisibility (see Chapter 6)
are of assistance in determining whether numbers have any
factors, but for really large numbers the process of elimin-
ation is an extremely wearisome business. Nevertheless,
although no simple general test is available, the search for
such a test has revealed many hitherto unknown number
relationships and has therefore not been unproductive.

In testing for factors, there is of course no need to test for
any possible factors greater than the square root of the num-
ber. For, if ¥ be the nearest whole number to the value of the
square root of y and if no numbers smaller than x will divide
exactly into_y, then no other number greater than x can divide
exactly into » so as to give another factor smaller than .

An ancient pictorial method of segregating prime numbers
from other numbers (called Composite numbers) was the use
of the Sieve of Eratosthenes. All numbers from 1 to any par-
ticular maximum number were written down and subjected
to a process of elimination as follows. All even numbers
greater than 2 and all numbers ending in o or 5 (other than
5 itself) were crossed out. Then, in turn, every third number
after 3, every seventh number after 7, every eleventh number

46

 

oy