

 This page uses content from Wikipedia. The original article was at Wieferich prime. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



In number theory, a Wieferich prime is a prime number  p  such that  p2  evenly divides  2(p − 1) − 1 .



It is conjectured that there are infinitely many Wieferich primes, but as of March 2021,only two have been identified.



Task 
 Write a routine (function procedure, whatever) to find Wieferich primes.
 Use that routine to identify and display all of the Wieferich primes less than 5000.


See also
 OEIS A001220 - Wieferich primes


with Ada.Text_IO;
 
procedure Wieferich_Primes is
 
   function Is_Prime (V : Positive) return Boolean is
      D : Positive := 5;
   begin
      if V < 2       then return False; end if;
      if V mod 2 = 0 then return V = 2; end if;
      if V mod 3 = 0 then return V = 3; end if;
      while D * D <= V loop
         if V mod D = 0 then
            return False;
         end if;
         D := D + 2;
      end loop;
      return True;
   end Is_Prime;
 
   function Is_Wieferich (N : Positive) return Boolean is
      Q : Natural := 1;
   begin
      if not Is_Prime (N) then
         return False;
      end if;
      for P in 2 .. N loop
         Q := (2 * Q) mod N**2;
      end loop;
      return Q = 1;
   end Is_Wieferich;
 
begin
 
   Ada.Text_IO.Put_Line ("Wieferich primes below 5000:");
   for N in 1 .. 4999 loop
      if Is_Wieferich (N) then
         Ada.Text_IO.Put_Line (N'Image);
      end if;
   end loop;
 
end Wieferich_Primes;