Anonymous user
Circular primes: Difference between revisions
m
→{{header|Free Pascal}}: small changes not time relevant
(→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:
=={{header|Pascal}}==
==={{header|Free Pascal}}===
Only test up to
Using a base 4 downcounter to create the numbers with more than one digit.
<lang pascal>{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
uses
Sysutils;
{$ENDIF}
{$IFDEF Delphi}
uses
System.Sysutils;
{$ENDIF}
{$IFDEF WINDOWS}
{$APPTYPE CONSOLE}
{$ENDIF}
const
MAXCNTOFDIGITS =
MAXDGTVAL = 3;
conv : array[0..MAXDGTVAL+1] of byte = (9,7,3,1,0);
type
tDigits = array[0..
tUint64 = NativeUint;
var
digits,
Pot10 : array[0..19] of tUint64;
CheckNum : array[0..19] of tUint64;
Line 1,670 ⟶ 1,676:
Count : tUint64;
function
// no multiples of 2,5▼
const
▲// no multiples of 2,3,5 weres tested
wheeldiff : array[0..7] of Uint32 = (+6,+4,+2,+4,+2,+4,+6,+2);
var
Line 1,682 ⟶ 1,688:
else
begin
IF Not(odd(n))then
EXIT(false);
IF (n mod 3 = 0 )then
EXIT(false);
IF (n mod 5 = 0 )then
EXIT(false);
result := true;
p := 1;
flipflop :=
repeat
while result do▼
Begin▼
p += wheeldiff[flipflop];
if p*p>n then
BREAK;
result := n mod p <> 0;
flipflop
end▼
end
end;
Line 1,705 ⟶ 1,711:
CheckInList := true;
end;
procedure CheckOne(MaxIdx:integer);
var
i,j,cv : integer;▼
Num,First : tUint64;
▲ i,j,cv : integer;
begin
i:= MaxIdx;
j := 0;
Num := 0;
repeat
cv := conv[digits[i]];
num := num*10+cv;
inc(j);
dec(i);
until i < 0;
First := num;
//first create circular numbers to minimize prime checks
//if one of the circled number must have been tested before
j := 0;
repeat
cv := revDigits[i];
Num := (Num -
//num was checked before
if num < First then
Line 1,737 ⟶ 1,744:
inc(j);
inc(i);
until i >=
//writeln(first,' ',num);//First and Last
If
Begin
repeat
dec(j);
IF Not(
EXIT;
until j = 0;
Line 1,753 ⟶ 1,760:
var
T0: Int64;
idx,MaxIDx,dgt : NativeInt;
Pot_ten : tUint64;
begin
T0 := GetTickCount64;
fillchar(digits,Sizeof(digits),chr(MAXDGTVAL));
Pot_ten := 1;
Line 1,763 ⟶ 1,772:
Pot_ten := Pot_ten*10;
end;
writeln(' Digits found time in ms');
Count :=0;
For idx := 2 to 10 do
if
begin
Found[Count]:= idx;
Line 1,786 ⟶ 1,797:
digits[idx] := dgt
else
Maxidx := idx;
writeln(idx:7,count:7,GetTickCount64-T0:8);
▲ end;
until false;
T0 := GetTickCount64-T0;
For idx := 0 to count-
writeln(Found[count-1]);
end.</lang>▼
writeln('It took ',T0,' ms ','to check ',MAXCNTOFDIGITS,' decimals');
{$IFDEF WINDOWS}
readln;
{$ENDIF}
end.
{{Out|@ Tio.Run}}
<pre>
Digits found time in ms
2 9
3 13
4 15
5 17
6 19
7 19
8 19 37
9 19
10 19
2,3,5,7,11,13,17,37,79,113,197,199,337,1193,3779,11939,19937,193939,199933
It took 21735 ms to check 11 decimals
</pre>
| |||