Circular primes: Difference between revisions

Content added Content deleted
(→‎Embedded: Now use the Wren-gmp module rather than a custom C program.)
m (→‎{{header|Free Pascal}}: small changes not time relevant)
Line 1,646: Line 1,646:
=={{header|Pascal}}==
=={{header|Pascal}}==
==={{header|Free Pascal}}===
==={{header|Free Pascal}}===
Only test up to 10 Digit numbers.RepUnit test with gmp to boring.<BR>
Only test up to 11 Digit numbers.RepUnit test with gmp to boring.<BR>
Using a base 4 downcounter to create the numbers with more than one digit.
Using a base 4 downcounter to create the numbers with more than one digit.
<lang pascal>{$IFDEF FPC}
<lang pascal>{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
uses
Sysutils;
{$ENDIF}
{$ENDIF}
{$IFDEF Delphi}
uses
System.Sysutils;
{$ENDIF}

{$IFDEF WINDOWS}
{$IFDEF WINDOWS}
{$APPTYPE CONSOLE}
{$APPTYPE CONSOLE}
{$ENDIF}
{$ENDIF}

const
const
MAXCNTOFDIGITS = 6;//10;//11
MAXCNTOFDIGITS = 11;
MAXDGTVAL = 3;
MAXDGTVAL = 3;
conv : array[0..MAXDGTVAL+1] of byte = (9,7,3,1,0);
conv : array[0..MAXDGTVAL+1] of byte = (9,7,3,1,0);
type
type
tDigits = array[0..47] of byte;
tDigits = array[0..23] of byte;
tUint64 = NativeUint;
tUint64 = NativeUint;
var
var
digits,
digits,
rotdigits : tDigits;
revDigits : tDigits;
Pot10 : array[0..19] of tUint64;
Pot10 : array[0..19] of tUint64;
CheckNum : array[0..19] of tUint64;
CheckNum : array[0..19] of tUint64;
Line 1,670: Line 1,676:
Count : tUint64;
Count : tUint64;


function isPrimeSpecial(n:tUint64):boolean;
function isPrime(n:tUint64):boolean;
⚫
// no multiples of 2,5
const
const
⚫
// no multiples of 2,3,5 weres tested
wheeldiff : array[0..7] of Uint32 = (+6,+4,+2,+4,+2,+4,+6,+2);
wheeldiff : array[0..7] of Uint32 = (+6,+4,+2,+4,+2,+4,+6,+2);
var
var
Line 1,682: Line 1,688:
else
else
begin
begin
IF Not(odd(n))then
EXIT(false);
IF (n mod 3 = 0 )then
IF (n mod 3 = 0 )then
EXIT(false);
IF (n mod 5 = 0 )then
EXIT(false);
EXIT(false);
result := true;
result := true;
p := 1;
p := 1;
flipflop := 6;
flipflop := 0;
repeat

⚫
while result do
⚫
Begin
p += wheeldiff[flipflop];
p += wheeldiff[flipflop];
if p*p>n then
if p*p>n then
BREAK;
BREAK;
result := n mod p <> 0;
result := n mod p <> 0;
flipflop -= 1;
flipflop := (flipflop+1) AND 7;
⚫
until NOT(result);
if flipflop<0 then
flipflop :=7;
⚫
end
end
end
end;
end;
Line 1,705: Line 1,711:
CheckInList := true;
CheckInList := true;
end;
end;

procedure CheckOne(MaxIdx:integer);
procedure CheckOne(MaxIdx:integer);
var
var
pRot : pbyte;
⚫
i,j,cv : integer;
Num,First : tUint64;
Num,First : tUint64;
⚫
i,j,cv : integer;

begin
begin
pRot := @rotDigits[0];
i:= MaxIdx;
i:= MaxIdx;
inc(maxIdx);
j := 0;
j := 0;
Num := 0;
Num := 0;
repeat
repeat
cv := conv[digits[i]];
cv := conv[digits[i]];
dec(i);
revDigits[j]:= cv;

pRot[j]:= cv;
num := num*10+cv;
num := num*10+cv;
pRot[j+MaxIdx]:= cv;
inc(j);
inc(j);
dec(i);
until i < 0;
until i < 0;
First := num;


//first create circular numbers to minimize prime checks
//first create circular numbers to minimize prime checks
//if one of the circled number must have been tested before
i := MaxIdx;
First := num;
i := 0;
j := 0;
j := 0;
repeat
repeat
cv := revDigits[i];
Num := (Num - rotDigits[i-MaxIdx]*Pot10[MaxIdx-1])*10+rotDigits[i];
Num := (Num - cv*Pot10[MaxIdx])*10+cv;
//num was checked before
//num was checked before
if num < First then
if num < First then
Line 1,737: Line 1,744:
inc(j);
inc(j);
inc(i);
inc(i);
until i >= 2*MaxIdx-1;
until i >= MaxIdx;
//writeln(first,' ',num);//First and Last

If isPrimeSpecial(First) then
If isPrime(First) then
Begin
Begin
repeat
repeat
dec(j);
dec(j);
IF Not(isPrimeSpecial(CheckNum[j])) then
IF Not(isPrime(CheckNum[j])) then
EXIT;
EXIT;
until j = 0;
until j = 0;
Line 1,753: Line 1,760:


var
var
T0: Int64;
idx,MaxIDx,dgt : NativeInt;
idx,MaxIDx,dgt : NativeInt;
Pot_ten : tUint64;
Pot_ten : tUint64;
begin
begin
T0 := GetTickCount64;
fillchar(digits,Sizeof(digits),chr(MAXDGTVAL));
fillchar(digits,Sizeof(digits),chr(MAXDGTVAL));
Pot_ten := 1;
Pot_ten := 1;
Line 1,763: Line 1,772:
Pot_ten := Pot_ten*10;
Pot_ten := Pot_ten*10;
end;
end;
writeln(' Digits found time in ms');
Count :=0;
For idx := 2 to 10 do
For idx := 2 to 10 do
if isPrimeSpecial(idx) then
if isPrime(idx) then
begin
begin
Found[Count]:= idx;
Found[Count]:= idx;
Line 1,786: Line 1,797:
digits[idx] := dgt
digits[idx] := dgt
else
else
⚫
begin
Maxidx := idx;
Maxidx := idx;
writeln(idx:7,count:7,GetTickCount64-T0:8);
⚫
end;
until false;
until false;
T0 := GetTickCount64-T0;
CheckOne(MaxIdx);
For idx := 0 to count-1 do
For idx := 0 to count-2 do
writeln(idx+1:5,Found[idx]:12);
write(Found[idx],',');
writeln(Found[count-1]);
⚫
end.</lang>
writeln('It took ',T0,' ms ','to check ',MAXCNTOFDIGITS,' decimals');
{$IFDEF WINDOWS}
readln;
{$ENDIF}
end.
⚫
</lang>
{{Out|@ Tio.Run}}
{{Out|@ Tio.Run}}
<pre>
<pre>
Digits found time in ms
1 2
2 3
2 9 0
3 5
3 13 0
4 7
4 15 0
5 11
5 17 0
6 13
6 19 1
7 17
7 19 5
8 37
8 19 37
9 79
9 19 255
10 113
10 19 2384
2,3,5,7,11,13,17,37,79,113,197,199,337,1193,3779,11939,19937,193939,199933
11 197
It took 21735 ms to check 11 decimals
12 199
13 337
14 1193
15 3779
16 11939
17 19937
18 193939
19 199933

Real time: 0.073 s digit Count MAXCNTOFDIGITS = 6;
Real time: 2.691 s digit Count MAXCNTOFDIGITS = 10;
Real time: 24.545 s digit Count MAXCNTOFDIGITS = 11;
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Circular_primes"