Carmichael 3 strong pseudoprimes: Difference between revisions

Content added Content deleted
Line 18: Line 18:
:::<tt>next d if (Prime<sub>2</sub>*Prime<sub>3</sub>) mod (Prime<sub>1</sub>-1) not equal 1</tt>
:::<tt>next d if (Prime<sub>2</sub>*Prime<sub>3</sub>) mod (Prime<sub>1</sub>-1) not equal 1</tt>
:::<tt>Prime<sub>1</sub> * Prime<sub>2</sub> * Prime<sub>3</sub> is a Carmichael Number</tt>
:::<tt>Prime<sub>1</sub> * Prime<sub>2</sub> * Prime<sub>3</sub> is a Carmichael Number</tt>

=={{header|Ada}}==

Uses the Miller_Rabin package from
[[http://rosettacode.org/wiki/Miller-Rabin_primality_test#ordinary_integers]].
<lang Ada>with Ada.Text_IO, Miller_Rabin;

procedure Nemesis is

type Number is range 0 .. 2**40-1; -- sufficiently large for the task

function Is_Prime(N: Number) return Boolean is
package MR is new Miller_Rabin(Number); use MR;
begin
return MR.Is_Prime(N) = Probably_Prime;
end Is_Prime;

begin
for P1 in Number(2) .. 61 loop
if Is_Prime(P1) then
for H3 in Number(1) .. P1 loop
declare
G: Number := H3 + P1;
P2, P3: Number;
begin
Inner:
for D in 1 .. G-1 loop
if ((H3+P1) * (P1-1)) mod D = 0 and then
(-(P1 * P1)) mod H3 = D mod H3
then
P2 := 1 + ((P1-1) * G / D);
P3 := 1 +(P1*P2/H3);
if Is_Prime(P2) and then Is_Prime(P3)
and then (P2*P3) mod (P1-1) = 1
then
Ada.Text_IO.Put_Line
( Number'Image(P1) & " *" & Number'Image(P2) & " *" &
Number'Image(P3) & " = " & Number'Image(P1*P2*P3) );
end if;
end if;
end loop Inner;
end;
end loop;
end if;
end loop;
end Nemesis;</lang>

{{out}}
<pre> 3 * 11 * 17 = 561
5 * 29 * 73 = 10585
5 * 17 * 29 = 2465
5 * 13 * 17 = 1105
7 * 19 * 67 = 8911

... (the full output is 69 lines long) ...

61 * 271 * 571 = 9439201
61 * 241 * 421 = 6189121
61 * 3361 * 4021 = 824389441</pre>


=={{header|D}}==
=={{header|D}}==
Retrieved from "https://rosettacode.org/wiki/Carmichael_3_strong_pseudoprimes"