Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- -- Rosetta Code Task written in Ada
- -- Smallest number k such that k+2^m is composite for all m less than k
- -- https://rosettacode.org/wiki/Smallest_number_k_such_that_k%2B2%5Em_is_composite_for_all_m_less_than_k
- -- loosely translated from the Python solution
- -- November 2024, R. B. E. Mods by sjw.
- pragma Ada_2022;
- with Ada.Text_IO; -- use Ada.Text_IO;
- with Ada.Integer_Text_IO; -- use Ada.Integer_Text_IO;
- with GNATCOLL.GMP.Integers; use GNATCOLL.GMP.Integers;
- procedure Smallest_GMP is
- Big_0 : constant Big_Integer := Make ("0");
- Big_1 : constant Big_Integer := Make ("1");
- Big_2 : constant Big_Integer := Make ("2");
- Big_3 : constant Big_Integer := Make ("3");
- Big_4 : constant Big_Integer := Make ("4");
- Big_5 : constant Big_Integer := Make ("5");
- function Is_Prime (N : in Big_Integer) return Boolean is
- Candidate : Big_Integer;
- tmp : big_integer;
- begin
- if N < Big_2 then
- return False;
- end if;
- -- N mod Big_2
- get_mod (result => tmp, n => n, d => Big_2);
- if tmp = Big_0 then
- return N = Big_2;
- end if;
- -- N mod Big_3
- get_mod (result => tmp, n => n, d => Big_3);
- if tmp = Big_0 then
- return N = Big_3;
- end if;
- if N = Big_5 then
- return True;
- end if;
- set (candidate, to => big_5);
- loop
- -- N mod Candidate
- get_mod (result => tmp, n => n, d => candidate);
- if tmp = big_0 then
- return False;
- end if;
- add (to => Candidate, this => Big_2);
- -- N mod Candidate
- get_mod (result => tmp, n => n, d => candidate);
- if tmp = big_0 then
- return False;
- end if;
- add (to => Candidate, this => Big_4);
- multiply (result => tmp, op1 => candidate, op2 => candidate);
- exit when tmp > n;
- end loop;
- return True;
- end Is_Prime;
- type Powers_of_Two_Table is array (0 .. 5_200) of Big_Integer;
- -- 5200 is just a rough upper limit guess of how many I need
- Powers_of_Two : Powers_of_Two_Table;
- procedure Load_Powers_of_Two (Powers_of_Two : in out Powers_of_Two_Table) is
- begin
- for I in Powers_of_Two'Range loop
- if I = 0 then
- set (Powers_of_Two (I), to => Big_1);
- elsif I = 1 then
- set (Powers_of_Two (I), to => Big_2);
- else
- multiply
- (result => Powers_of_Two (I), op1 => Powers_of_Two (I - 1),
- op2 => big_2);
- end if;
- end loop;
- end Load_Powers_of_Two;
- procedure Show_Powers_of_Two (Powers_of_Two : in Powers_of_Two_Table) is
- begin
- for I in Powers_of_Two'Range loop
- Ada.Text_IO.Put_Line (image (Powers_of_Two (I)));
- end loop;
- end Show_Powers_of_Two;
- function Is_A033919
- (Powers_of_Two : in Powers_of_Two_Table; K : in Positive) return Boolean
- is
- N : Big_Integer;
- big_k : big_integer;
- tmp : big_integer;
- begin
- if K = 1 then
- return False;
- else
- set (big_k, to => gnatcoll.gmp.long (k));
- for M in 1 .. K - 1 loop
- -- N := Powers_of_Two (M) + big_K;
- set (tmp, to => powers_of_two (m));
- add (to => tmp, this => big_k);
- set (n, to => tmp);
- Ada.Text_IO.Put_Line
- ("k:" & K'Image & " m:" & M'Image & " n: " & image (N));
- if Is_Prime (N) then
- return False;
- end if;
- end loop;
- return True;
- end if;
- end Is_A033919;
- Sequence_Number : Natural := 0;
- Max_Sequence_Number : constant Positive := 5;
- J : Positive := 1;
- begin
- Load_Powers_of_Two (Powers_of_Two);
- loop
- if Is_A033919 (Powers_of_Two, J) then
- Sequence_Number := Sequence_Number + 1;
- Ada.Text_IO.Put ("*****An answer was found! ");
- Ada.Integer_Text_IO.Put (J, 5);
- Ada.Text_IO.Put (" ");
- Ada.Text_IO.New_Line;
- end if;
- exit when Sequence_Number >= Max_Sequence_Number;
- J := J + 2;
- end loop;
- end Smallest_GMP;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement