The first algorithm here deals with the question of whether a number is prime. The algorithm for this is fairly simple: if the number in question divides by another number with zero remainder then the number is not prime.
There is no need to investigate numbers greater than half the number in question because, for example, 24 cannot divide by 13 with zero remainder. In fact the limit is less than half, it is the square root of the number in question. Take 49. It doesn't divide by 2, 3, 4, 5 or 6 but it does divide by 7. 49 clearly does not divide by any multiple of 2, 3, 4, 5 or 6, but might it divide by 11? It clearly cannot divide by 11 either because any divisor greater than the square root will multiply out to something greater than the number (7*11=77).
As Pascal is strongly typed and the square root function (sqrt) takes a floating point value as its parameter we cannot use the square root function with an integer type (we could do this in a weakly typed language such as Javascript - see here for details).
In the code below we introduce a Boolean variable, prime, which we set to true - we assume that the number entered by the user is prime. The while loop sets out to establish whether this assumption is true. If it finds a number that divides into that entered by the user then it sets prime to false and records the value of the divisor at that point. At this point the while loop stops because the condition (prime) is no longer true.
The procedure finishes by using the value of prime to determine the final message, whether or not the number was prime and what its first divisor was.
procedure TForm1.Button1Click(Sender: TObject);
var
value, divisor, valuediv2 : integer;
prime:Boolean;
begin
prime := true;
lastdivisor:=0; //initialise in case
not assigned later
divisor :=2; //no need to divide by 1
if (edit1.Text='') then showmessage('You must enter a value')
else
begin
value:=strtoint(edit1.Text);
valuediv2:=value div 2; //do this here
instead of putting in the expression in the next line
while (divisor <= valuediv2) and (prime) do
begin
if value mod divisor = 0 then
prime:=false
else
inc(divisor);
end;
if prime then edit2.Text:=inttostr(value)+' is prime'
else edit2.text:=inttostr(value)+' is not prime, it divides by ' +
inttostr(divisor);
edit1.setfocus; //put
cursor in edit box ready for next value
end;
end;
Another problem associated with numbers concerns finding their prime factors - the prime numbers which, when multiplied together, produce the first number.
procedure TForm1.Button3Click(Sender: TObject);
var
divisor, user_value, replica:integer;
prime:Boolean;
primestring:string;
begin
if not (edit1.Text='') then user_value:=strtoint(edit1.Text);
replica := user_value;
user_value:= replica div 2;
prime := true;
divisor := 2;
repeat
while (replica mod divisor = 0) do
begin
primestring:= primestring+inttostr(divisor)+' ';
replica := replica div divisor;
end;
inc (divisor);
until (replica = 1) or (divisor > user_value);
if replica < user_value then prime := false;
if not prime then edit3.Text:=primestring
else edit3.Text:=inttostr(user_value) + ' is prime and has no factors
other than 1 and itself.';
edit1.setfocus;
end;
In this code we make a copy of the number entered by the user (replica) because the value of user_value is reduced by div 2 inside the repeat loop.
The third algorithm concerning prime numbers is the one which finds all prime numbers up to a certain limit. The algorithm for this is as follows:
for every number from 2 to the limit do
test if the current number is prime
We start at 2 because we are not interested in whether 1 is prime.
To test if a number is prime we repeatedly divide the current number by a divisor that runs from 2 to 1 less than the current value of the number. We set a Boolean variable prime to be true and we set it to false if the number divides by the divisor with 0 remainder. One condition for the test is that the divisor is less than the number: if they are the same the result of i mod divisor will obviously be zero. A second condition is that prime is true: once a result of 0 is found then prime is false and the test can stop.
The code:
procedure TForm1.Button4Click(Sender: TObject);
var
i,j, limit, divisor : integer;
prime:Boolean;
primestring:string;
begin
if not (edit1.Text='') then limit:=strtoint(edit1.Text);
for i:=2 to limit do
//go through every number
begin
divisor:=2; //set divisor to 2
for each inner loop
prime:=true; //assume number is prime
while (divisor < i) and (prime) do
//stop when divisor >= i or prime not true
begin
if i mod divisor = 0 then prime := false;
//number divides by something so is not prime
inc (divisor); //try next
divisor
end; //while
if prime then memo1.Lines.Add(inttostr(i));
end; //for
edit1.setfocus;
end;
If the limit is 10 the sequence of numbers will be as follows:
first number to try (i) = 2, divisor = 2,
i and divisor are equal so condition divisor < i fails
second number to try (i) = 3, divisor = 2
3 mod 2 = 1 so prime remains true
divisor incremented to 3 so condition divisor < i fails
third number to try (i) = 4, divisor = 2;
4 mod 2 = 0, so prime goes to false
fourth number to try (i) = 5, divisor = 2
5 mod 2 = 1 so prime remains true
divisor incremented to 3
5 mod 3 = 2 so prime remains true
divisor incremented to 4
5 mod 4 = 1 so prime remains true
divisor incremented to 5 so condition divisor < i fails
