Anonymous user
Circular primes: Difference between revisions
→{{header|Perl}}: perpend =={{header|Pascal}}== test up to 10 digits
(→{{header|Ruby}}: Add Ruby) |
(→{{header|Perl}}: perpend =={{header|Pascal}}== test up to 10 digits) |
||
Line 1,644:
R(49081) is probably prime.</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
Only test up to 10 Digit numbers.RepUnit test with gmp to boring.<BR>
Using a base 4 downcounter to create the numbers with more than one digit.
<lang pascal>{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$ENDIF}
{$IFDEF WINDOWS}
{$APPTYPE CONSOLE}
{$ENDIF}
const
MAXCNTOFDIGITS = 10;
MAXDGTVAL = 3;
conv : array[0..MAXDGTVAL+1] of byte = (9,7,3,1,0);
type
tDigits = array[0..47] of byte;
tUint64 = NativeUint;
var
digits,
rotdigits : tDigits;
Pot10 : array[0..19] of tUint64;
CheckNum : array[0..19] of tUint64;
Found : array[0..24] of tUint64;
Count : tUint64;
function isPrimeSpecial(n:tUint64):boolean;
// no multiples of 2,5
const
wheeldiff : array[0..7] of Uint32 = (+6,+4,+2,+4,+2,+4,+6,+2);
var
p: tUint64;
flipflop : Int32;
begin
if n< 32 then
EXIT(n in [2,3,5,7,11,13,17,19,23,29,31])
else
begin
IF (n mod 3 = 0 )then
EXIT(false);
result := true;
p := 1;
flipflop := 6;
while result do
Begin
p += wheeldiff[flipflop];
if p*p>n then
BREAK;
result := n mod p <> 0;
flipflop -= 1;
if flipflop<0 then
flipflop :=7;
end
end
end;
function CheckInList(num:tUint64;MaxIdx:integer):Boolean;
Begin
CheckInList := true;
end;
procedure CheckOne(MaxIdx:integer);
var
pRot : pbyte;
i,j,cv : integer;
Num,First : tUint64;
begin
pRot := @rotDigits[0];
i:= MaxIdx;
inc(maxIdx);
j := 0;
Num := 0;
repeat
cv := conv[digits[i]];
dec(i);
pRot[j]:= cv;
num := num*10+cv;
pRot[j+MaxIdx]:= cv;
inc(j);
until i < 0;
//first create circular numbers to minimize prime checks
i := MaxIdx;
First := num;
j := 0;
repeat
Num := (Num - rotDigits[i-MaxIdx]*Pot10[MaxIdx-1])*10+rotDigits[i];
//num was checked before
if num < First then
EXIT;
CheckNum[j] := num;
inc(j);
inc(i);
until i >= 2*MaxIdx-1;
If isPrimeSpecial(First) then
Begin
repeat
dec(j);
IF Not(isPrimeSpecial(CheckNum[j])) then
EXIT;
until j = 0;
cv := Count;
Found[cv] := First;
inc(count);
end;
end;
var
idx,MaxIDx,dgt : NativeInt;
Pot_ten : tUint64;
begin
fillchar(digits,Sizeof(digits),chr(MAXDGTVAL));
Pot_ten := 1;
For idx := Low(Pot10) to High(Pot10) do
begin
Pot10[idx] := Pot_ten;
Pot_ten := Pot_ten*10;
end;
For idx := 2 to 10 do
if isPrimeSpecial(idx) then
begin
Found[Count]:= idx;
inc(count);
end;
maxIdx := 1;
repeat
CheckOne(MaxIdx);
idx := 0;
repeat
dgt := digits[idx]-1;
if dgt >=0 then
break;
digits[idx] := MAXDGTVAL;
inc(idx);
until idx >MAXCNTOFDIGITS-1;
if idx > MAXCNTOFDIGITS-1 then
BREAK;
if idx<=MaxIDX then
digits[idx] := dgt
else
Maxidx := idx;
until false;
CheckOne(MaxIdx);
For idx := 0 to count-1 do
writeln(idx+1:5,Found[idx]:12);
end.</lang>
{{Out|@ Tio.Run}}
<pre>
1 2
2 3
3 5
4 7
5 11
6 13
7 17
8 37
9 79
10 113
11 197
12 199
13 337
14 1193
15 3779
16 11939
17 19937
18 193939
19 199933
Real time: 2.691 s CPU share: 99.44 %
one digit more MAXCNTOFDIGITS = 11;
Real time: 24.545 s</pre>
=={{header|Perl}}==
{{trans|Raku}}
| |||