77 lines
1.7 KiB
Ada
77 lines
1.7 KiB
Ada
with Ada.Text_IO; with Ada.Integer_Text_IO;
|
|
with Ada.Strings.Fixed;
|
|
|
|
procedure Totient is
|
|
|
|
function Totient (N : in Integer) return Integer is
|
|
Tot : Integer := N;
|
|
I : Integer;
|
|
N2 : Integer := N;
|
|
begin
|
|
I := 2;
|
|
while I * I <= N2 loop
|
|
if N2 mod I = 0 then
|
|
while N2 mod I = 0 loop
|
|
N2 := N2 / I;
|
|
end loop;
|
|
Tot := Tot - Tot / I;
|
|
end if;
|
|
|
|
if I = 2 then
|
|
I := 1;
|
|
end if;
|
|
I := I + 2;
|
|
end loop;
|
|
|
|
if N2 > 1 then
|
|
Tot := Tot - Tot / N2;
|
|
end if;
|
|
|
|
return Tot;
|
|
end Totient;
|
|
|
|
Count : Integer := 0;
|
|
Tot : Integer;
|
|
Placeholder : String := " n Phi Is_Prime";
|
|
Image_N : String renames Placeholder ( 1 .. 3);
|
|
Image_Phi : String renames Placeholder ( 6 .. 8);
|
|
Image_Prime : String renames Placeholder (11 .. Placeholder'Last);
|
|
use Ada.Text_IO;
|
|
use Ada.Integer_Text_IO;
|
|
|
|
Last : constant := 25;
|
|
begin
|
|
|
|
Put_Line (Placeholder);
|
|
|
|
for N in 1 .. Last loop
|
|
Tot := Totient (N);
|
|
|
|
if N - 1 = Tot then
|
|
Count := Count + 1;
|
|
end if;
|
|
Put (Image_N, N);
|
|
Put (Image_Phi, Tot);
|
|
Image_Prime := Ada.Strings.Fixed.Tail
|
|
(Source => (if N - 1 = Tot then True'Image else False'Image),
|
|
Count => Image_Prime'Length);
|
|
Put_Line (Placeholder);
|
|
end loop;
|
|
New_Line;
|
|
|
|
Put_Line ("Number of primes up to " & Last'Image &" =" & Count'Image);
|
|
|
|
for N in Last + 1 .. 100_000 loop
|
|
Tot := Totient (N);
|
|
|
|
if Tot = N - 1 then
|
|
Count := Count + 1;
|
|
end if;
|
|
|
|
if N = 100 or N = 1_000 or N mod 10_000 = 0 then
|
|
Put_Line ("Number of primes up to " & N'Image & " =" & Count'Image);
|
|
end if;
|
|
end loop;
|
|
|
|
end Totient;
|