Advertisement
SimonWright

Rosetta code problem with GNATCOLL_GMP

Nov 4th, 2024
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Ada 4.17 KB | Source Code | 0 0
  1. -- Rosetta Code Task written in Ada
  2. -- Smallest number k such that k+2^m is composite for all m less than k
  3. -- https://rosettacode.org/wiki/Smallest_number_k_such_that_k%2B2%5Em_is_composite_for_all_m_less_than_k
  4. -- loosely translated from the Python solution
  5. -- November 2024, R. B. E. Mods by sjw.
  6.  
  7. pragma Ada_2022;
  8. with Ada.Text_IO; -- use Ada.Text_IO;
  9. with Ada.Integer_Text_IO; -- use Ada.Integer_Text_IO;
  10. with GNATCOLL.GMP.Integers; use GNATCOLL.GMP.Integers;
  11.  
  12. procedure Smallest_GMP is
  13.  
  14.    Big_0 : constant Big_Integer := Make ("0");
  15.    Big_1 : constant Big_Integer := Make ("1");
  16.    Big_2 : constant Big_Integer := Make ("2");
  17.    Big_3 : constant Big_Integer := Make ("3");
  18.    Big_4 : constant Big_Integer := Make ("4");
  19.    Big_5 : constant Big_Integer := Make ("5");
  20.  
  21.    function Is_Prime (N : in Big_Integer) return Boolean is
  22.       Candidate : Big_Integer;
  23.       tmp       : big_integer;
  24.    begin
  25.       if N < Big_2 then
  26.          return False;
  27.       end if;
  28.       --  N mod Big_2
  29.       get_mod (result => tmp, n => n, d => Big_2);
  30.       if tmp = Big_0 then
  31.          return N = Big_2;
  32.       end if;
  33.       --  N mod Big_3
  34.       get_mod (result => tmp, n => n, d => Big_3);
  35.       if tmp = Big_0 then
  36.          return N = Big_3;
  37.       end if;
  38.       if N = Big_5 then
  39.          return True;
  40.       end if;
  41.       set (candidate, to => big_5);
  42.       loop
  43.          --  N mod Candidate
  44.          get_mod (result => tmp, n => n, d => candidate);
  45.          if tmp = big_0 then
  46.             return False;
  47.          end if;
  48.          add (to => Candidate, this => Big_2);
  49.          --  N mod Candidate
  50.          get_mod (result => tmp, n => n, d => candidate);
  51.          if tmp = big_0 then
  52.             return False;
  53.          end if;
  54.          add (to => Candidate, this => Big_4);
  55.  
  56.          multiply (result => tmp, op1 => candidate, op2 => candidate);
  57.          exit when tmp > n;
  58.       end loop;
  59.       return True;
  60.    end Is_Prime;
  61.  
  62.    type Powers_of_Two_Table is array (0 .. 5_200) of Big_Integer;
  63.    -- 5200 is just a rough upper limit guess of how many I need
  64.    Powers_of_Two : Powers_of_Two_Table;
  65.  
  66.    procedure Load_Powers_of_Two (Powers_of_Two : in out Powers_of_Two_Table) is
  67.    begin
  68.       for I in Powers_of_Two'Range loop
  69.          if I = 0 then
  70.             set (Powers_of_Two (I), to => Big_1);
  71.          elsif I = 1 then
  72.             set (Powers_of_Two (I), to => Big_2);
  73.          else
  74.             multiply
  75.               (result => Powers_of_Two (I), op1 => Powers_of_Two (I - 1),
  76.                op2    => big_2);
  77.          end if;
  78.       end loop;
  79.    end Load_Powers_of_Two;
  80.  
  81.    procedure Show_Powers_of_Two (Powers_of_Two : in Powers_of_Two_Table) is
  82.    begin
  83.       for I in Powers_of_Two'Range loop
  84.          Ada.Text_IO.Put_Line (image (Powers_of_Two (I)));
  85.       end loop;
  86.    end Show_Powers_of_Two;
  87.  
  88.    function Is_A033919
  89.      (Powers_of_Two : in Powers_of_Two_Table; K : in Positive) return Boolean
  90.    is
  91.       N     : Big_Integer;
  92.       big_k : big_integer;
  93.       tmp   : big_integer;
  94.    begin
  95.       if K = 1 then
  96.          return False;
  97.       else
  98.          set (big_k, to => gnatcoll.gmp.long (k));
  99.          for M in 1 .. K - 1 loop
  100.             --  N := Powers_of_Two (M) + big_K;
  101.             set (tmp, to => powers_of_two (m));
  102.             add (to => tmp, this => big_k);
  103.             set (n, to => tmp);
  104.             Ada.Text_IO.Put_Line
  105.               ("k:" & K'Image & " m:" & M'Image & " n: " & image (N));
  106.             if Is_Prime (N) then
  107.                return False;
  108.             end if;
  109.          end loop;
  110.          return True;
  111.       end if;
  112.    end Is_A033919;
  113.  
  114.    Sequence_Number     : Natural           := 0;
  115.    Max_Sequence_Number : constant Positive := 5;
  116.    J                   : Positive          := 1;
  117.  
  118. begin
  119.    Load_Powers_of_Two (Powers_of_Two);
  120.    loop
  121.       if Is_A033919 (Powers_of_Two, J) then
  122.          Sequence_Number := Sequence_Number + 1;
  123.          Ada.Text_IO.Put ("*****An answer was found!  ");
  124.          Ada.Integer_Text_IO.Put (J, 5);
  125.          Ada.Text_IO.Put (" ");
  126.          Ada.Text_IO.New_Line;
  127.       end if;
  128.       exit when Sequence_Number >= Max_Sequence_Number;
  129.       J := J + 2;
  130.    end loop;
  131. end Smallest_GMP;
  132.  
Tags: bigInteger
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement