Circular primes: Difference between revisions

Content added Content deleted
m (→‎{{header|Free Pascal}}: using gmp for prime testing.Speeds up from 21735 ms downto 444ms for 11 digits)
m (→‎{{header|Free Pascal}}: runtime 44% of before.Change counter so no no smaller digit than the first is used.Tested numbers mod 3/7 to speed up.)
Line 1,647: Line 1,647:
==={{header|Free Pascal}}===
==={{header|Free Pascal}}===
Only test up to 14 digit numbers.RepUnit test with gmp is to boring.<BR>
Only test up to 14 digit numbers.RepUnit test with gmp is 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.<br>
Changed the manner of the counter, so that it counts that there is no digit smaller than the first.
199-> 333 and not 311 so a base4 counter 1_(1,3,7,9) changed to base3 3_( 3,7,9 )->base2 7_(7,9) -> base 1 = 99....99.
The main speed up is reached by testing with small primes within CycleNum.
<lang pascal>
<lang pascal>
program CircularPrimes
program CircularPrimes;
//nearly the way it is done:
//nearly the way it is done:
//http://www.worldofnumbers.com/circular.htm
//http://www.worldofnumbers.com/circular.htm
//base 4 counter to create numbers
//base 4 counter to create numbers with first digit is the samallest used.
//check if numbers are tested before
//check if numbers are tested before and reduce gmp-calls by checking with prime 3,7

//test if prime
{$IFDEF FPC}
{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
Line 1,679: Line 1,682:
digits,
digits,
revDigits : tDigits;
revDigits : tDigits;
Pot10 : array[0..19] of tUint64;
CheckNum : array[0..19] of tUint64;
CheckNum : array[0..19] of tUint64;
Found : array[0..24] of tUint64;
Found : array[0..23] of tUint64;
Count,CountNumCyc,CountNumPrmTst : tUint64;
Pot_ten,Count,CountNumCyc,CountNumPrmTst : tUint64;

procedure CheckOne(MaxIdx:integer);
var
Num : Uint64;
i : integer;
begin
i:= MaxIdx;
repeat
inc(CountNumPrmTst);
num := CheckNum[i];
mpz_set_ui(mpz,Num);
If mpz_probab_prime_p(mpz,3)=0then
EXIT;
dec(i);
until i < 0;
Found[Count] := CheckNum[0];
inc(count);
end;


function CycleNum(MaxIdx:integer):Boolean;
function CycleNum(MaxIdx:integer):Boolean;
//first create circular numbers to minimize prime checks
//create the number and cycle it, if neccessary
var
var
Num,First,P10 : tUint64;
cycNum,First,P10 : tUint64;
i,j,cv : integer;
i,j,cv : integer;
Begin
Begin
j := 1;
i:= MaxIdx;
i:= MaxIdx-1;
j := 0;
P10 := Pot10[MaxIdx];
First := 0;

first := conv[digits[MaxIdx]];
num := first;
revDigits[0] := first;

repeat
repeat
cv := conv[digits[i]];
cv := conv[digits[i]];
dec(i);
dec(i);
First := First*10+cv;
//smaller digit then the first
if first>cv then
EXIT(false);
revDigits[j]:= cv;
revDigits[j]:= cv;
inc(j);
inc(j);
num := num*10+cv;
until i < 0;
until i < 0;
// if num is divisible by 3 then cycle numbers also divisible by 3 same sum of digits
IF First MOD 3 = 0 then
EXIT(false);
If First mod 7 = 0 then
EXIT(false);


//if one of the cycled number must have been tested before break
First := num;
P10 := Pot_ten;
//first create circular numbers to minimize prime checks
//if one of the circled number must have been tested before
i := 0;
i := 0;
j := 0;
j := 0;
CheckNum[j] := num;
CheckNum[j] := First;
cycNum := First;
repeat
repeat
inc(CountNumCyc);
inc(CountNumCyc);
cv := revDigits[i];
cv := revDigits[i];
Num := (Num - cv*P10)*10+cv;
//num was checked before? ala 37333 -> 33337
if num < First then
EXIT(false);
inc(j);
inc(j);
CheckNum[j] := num;
cycNum := (cycNum - cv*P10)*10+cv;
//num was checked before
if cycNum < First then
EXIT(false);
if cycNum mod 7 = 0 then
EXIT(false);
CheckNum[j] := cycNum;
inc(i);
inc(i);
until i >= MaxIdx;
until i >= MaxIdx;
Line 1,729: Line 1,748:
end;
end;


procedure CheckOne(MaxIdx:integer);
var
var
i : integer;
T0: Int64;
begin
i:= MaxIdx;
//writeln(first,' ',num);//First and Last
inc(CountNumPrmTst);
mpz_set_ui(mpz,CheckNum[i]);
If mpz_probab_prime_p(mpz,3)>0then
Begin
repeat
inc(CountNumPrmTst);
dec(i);
mpz_set_ui(mpz,CheckNum[i]);
IF mpz_probab_prime_p(mpz,3)=0 then
EXIT;
until i = 0;
Found[Count] := CheckNum[0];
inc(count);
end;
end;


idx,MaxIDx,dgt,MinDgt : NativeInt;
var
T0: Int64;
idx,MaxIDx,dgt : NativeInt;
Pot_ten : tUint64;
begin
begin
T0 := GetTickCount64;
T0 := GetTickCount64;
mpz_init(mpz);
mpz_init(mpz);

fillchar(digits,Sizeof(digits),chr(MAXDGTVAL));
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;
writeln(' Digits found time in ms');
Count :=0;
Count :=0;
For idx := 2 to 10 do
For maxIdx := 2 to 10 do
if isPrime(idx) then
if maxidx in[2,3,5,7] then
begin
begin
Found[Count]:= idx;
Found[Count]:= maxIdx;
inc(count);
inc(count);
end;
end;


Pot_ten := 10;
maxIdx := 1;
maxIdx := 1;
idx := 0;
MinDgt := MAXDGTVAL;
repeat
repeat
IF CycleNum(MaxIdx) then
if CycleNum(MaxIdx) then
CheckOne(MaxIdx);
CheckOne(MaxIdx);
idx := 0;
idx := 0;
repeat
repeat
Line 1,783: Line 1,777:
if dgt >=0 then
if dgt >=0 then
break;
break;
digits[idx] := MAXDGTVAL;
digits[idx] := MinDgt;
inc(idx);
inc(idx);
until idx >MAXCNTOFDIGITS-1;
until idx >MAXCNTOFDIGITS-1;

if idx > MAXCNTOFDIGITS-1 then
if idx > MAXCNTOFDIGITS-1 then
BREAK;
BREAK;

if idx<=MaxIDX then
if idx<=MaxIDX then
begin
digits[idx] := dgt
digits[idx] := dgt;
//change all to leading digit
if idx=MaxIDX then
Begin
For MinDgt := 0 to idx do
digits[MinDgt]:= dgt;
minDgt := dgt;
end;
end
else
else
begin
begin
minDgt := MAXDGTVAL;
For maxidx := 0 to idx do
digits[MaxIdx] := MAXDGTVAL;
Maxidx := idx;
Maxidx := idx;
Pot_ten := Pot_ten*10;
writeln(idx:7,count:7,CountNumCyc:16,CountNumPrmTst:12,GetTickCount64-T0:8);
writeln(idx:7,count:7,CountNumCyc:16,CountNumPrmTst:12,GetTickCount64-T0:8);
end;
end;
until false;
until false;
writeln(idx:7,count:7,CountNumCyc:15,CountNumPrmTst:12,GetTickCount64-T0:8);
writeln(idx:7,count:7,CountNumCyc:16,CountNumPrmTst:12,GetTickCount64-T0:8);
T0 := GetTickCount64-T0;
T0 := GetTickCount64-T0;


Line 1,813: Line 1,822:
<pre>
<pre>
Digits found cycles created primetests time in ms
Digits found cycles created primetests time in ms
2 9 10 15 1
2 9 7 10 0
3 13 70 56 1
3 13 43 38 0
4 15 360 150 1
4 15 203 89 0
5 17 1649 434 1
5 17 879 213 0
6 19 7352 1353 2
6 19 4209 816 1
7 19 31863 4194 4
7 19 16595 1794 2
8 19 136945 13945 12
8 19 67082 4666 6
9 19 582758 47441 35
9 19 270760 13108 19
10 19 2465108 166817 123
10 19 1094177 39059 63
11 19 10370018 593076 444
11 19 4421415 118787 220
12 19 43441098 2152361 1845
12 19 23728859 1078484 1505
13 19 181279015 7816548 7562
13 19 77952009 1869814 3562
14 19 754020918 28736408 26129
14 19 296360934 4405393 11320
#### 14 19 754020918 28736408 26129 ##### before
2,3,5,7,11,13,17,37,79,113,197,199,337,1193,3779,11939,19937,193939,199933
2,3,5,7,11,13,17,37,79,113,197,199,337,1193,3779,11939,19937,193939,199933
It took 26129 ms to check 14 decimals
It took 11320 ms to check 14 decimals

//It took 573 ms to check 14 decimals-> only creating 4^14 numbers
only creating numbers
//It took 6045 ms to check 14 decimals-> creating 4^14 numbers and cycle the numbers
14 4 0 0 184
</pre>
creating and cycling numbers testing not ( MOD 3=0 OR MoD 7 = 0)
14 4 247209700 0 8842
that reduces the count of gmp-prime tests to 1/6 </pre>


=={{header|Perl}}==
=={{header|Perl}}==
Retrieved from "https://rosettacode.org/wiki/Circular_primes"