-- file FermatBasic.Ada

-- primes by Fermat's method, Basic version


-- 08/05/24


procedure Square_Root(XX: in Integer; Try: in Integer;
				X: out Integer; R: out Integer) is
	-- X is the largest X such that X*X + R equals XX with R >= zero
	-- Try is initial guess which must be low 
	K, KK: Integer;
begin
	k := Try;
	loop
		KK := K*K;				-- KK is simply K squared
		if KK = XX then 
			X := K; R := 0; return;
		elsif KK > XX then
			X := K - 1; R := XX - X*X; return;
		end if;
		K := K+1;
	end loop;
end Square_Root;


with Square_Root;
procedure Fermat_Basic(N: in Integer; P, Q: out Integer) is
	X: Integer;
	Y: Integer;
	R: Integer;
	Try: Integer := 1;
begin
	Square_Root(N, 1, X, R);
	if R = 0 then
		-- N was a perfect square
		P := X; Q := X;
		return;
	end if;

	loop
		X := X + 1;
		Square_Root(X*X-N, Try, Y, R);
		if R = 0 then
			-- X*X-N was a perfect square
			P := X+Y; Q := X-Y;
			return;
		end if;
		Try := Y;
	end loop;
exception
	when others => P := 0; Q := 0;
end Fermat_Basic;





with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Fermat_Basic;
procedure Do_Fermat_Basic is
	N, P, Q: Integer;
begin	
	Put_Line("Welcome to Fermat's basic method");
	loop
<<Again>>
		begin			
			New_Line;
			Put("Insert number N = "); Get(N);
		exception 
			when others =>
				Put_Line("Number too big or not a number");
				Skip_Line; 
				goto Again;
		end;
		exit when N = 0;

		if N rem 4 = 2 then
			Put_Line("Algorithm fails on odd multiples of 2," &
					" so halving N"); 
			N := N/2;
			Put("New N = "); Put(N, 0); New_Line;
		end if;
		
		Fermat_Basic(N, P, Q);
		
		if P = 0 and Q = 0 then
			Put_Line("Overflowed internally");
			goto Again;
		end if;

		Put("Two factors are   "); Put(P, 0); Put("   "); Put(Q, 0); 
		New_Line;
	end loop;
	Put_Line("Goodbye");  Skip_Line(2);
end Do_Fermat_Basic;