Multi-base primes: Difference between revisions
Content added Content deleted
m (→Up to base 62: make sub item) |
m (→{{header|Pascal}}: using inc in base to speed up converting, CnvtoBase base was the true reason.) |
||
Line 634: | Line 634: | ||
First counting the bases that convert a MAXBASE string of n into a prime number.<BR> |
First counting the bases that convert a MAXBASE string of n into a prime number.<BR> |
||
Afterwards only checking the maxcount for the used bases.<BR> |
Afterwards only checking the maxcount for the used bases.<BR> |
||
Most time consuming is sieving for the primes. |
|||
<lang pascal>program MAXBaseStringIsPrimeInBase; |
<lang pascal>program MAXBaseStringIsPrimeInBase; |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
Line 646: | Line 645: | ||
sysutils; |
sysutils; |
||
const |
const |
||
CharOfBase= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'; |
|||
MINBASE = 2; |
MINBASE = 2; |
||
MAXBASE = |
MAXBASE = 62;//62;//36 |
||
MAXDIGITCOUNT = |
MAXDIGITCOUNT = 5;//6; |
||
type |
type |
||
tdigits = |
tdigits = record |
||
dgtDgts : array [0..13] of byte; |
|||
dgtMaxIdx, |
|||
dgtMaxDgtVal :byte; |
|||
dgtNum : Uint64; |
|||
end; |
|||
tSol = array of Uint64; |
tSol = array of Uint64; |
||
var |
var |
||
BoolPrimes: array of boolean; |
BoolPrimes: array of boolean; |
||
//memorize the highest used digit |
|||
function Out_String(n:Uint64;var s: AnsiString):Uint32;forward; |
|||
MaxDgtPos : UInt32; |
|||
procedure Out_Digits(const dgts:tDigits); |
|||
var |
|||
s : ANsistring; |
|||
i : Int32; |
|||
begin |
|||
s := ''; |
|||
with dgts do |
|||
Begin |
|||
i := dgtMaxIdx; |
|||
while i >= 0 do |
|||
begin |
|||
s := s+CharOfBase[dgtDgts[i]]; |
|||
dec(i); |
|||
end; |
|||
end; |
|||
write(#13,s); |
|||
end; |
|||
function BuildWheel(primeLimit:Int64):NativeUint; |
function BuildWheel(primeLimit:Int64):NativeUint; |
||
var |
var |
||
Line 742: | Line 766: | ||
end; |
end; |
||
procedure CnvtoMAXBASE(n:Uint64;var dgt:tDigits); |
|||
var |
var |
||
pQ :pQWord; |
|||
q,r: Uint64; |
q,r: Uint64; |
||
i: |
i : Int32; |
||
Begin |
Begin |
||
pQ := @dgt[0]; |
|||
pQ[0] := 0;pQ[1] := 0; |
|||
//aka fillChar(dgt[0],SizeOf(dgt),#0); |
|||
i := 0; |
i := 0; |
||
with dgt do |
|||
Begin |
|||
dgtNum:= n; |
|||
repeat |
|||
r := (n-q*MAXBASE); |
|||
r := n; |
|||
q := n div MAXBASE; |
|||
r -= q*MAXBASE; |
|||
n := q; |
n := q; |
||
dgtDgts[i] := r; |
|||
inc(i); |
|||
until (q = 0); |
|||
dec(i); |
|||
dgtMaxIdx := i; |
|||
r := 1; |
|||
repeat |
|||
q := dgtDgts[i]; |
|||
if r < q then |
|||
r := q; |
|||
dec(i); |
|||
until i <0 ; |
|||
dgtMaxDgtVal := r; |
|||
end; |
|||
end; |
end; |
||
function CnvtoBase(const dgt:tDigits;base:NativeUint |
function CnvtoBase(const dgt:tDigits;base:NativeUint):Uint64; |
||
var |
|||
tmpDgt,i: NativeInt; |
|||
Begin |
Begin |
||
result := 0; |
result := 0; |
||
with dgt do |
|||
repeat |
|||
Begin |
|||
result := base*result+dgt[DgtCnt]; |
|||
i:= dgtMaxIdx; |
|||
repeat |
|||
until (DgtCnt< 0); |
|||
//result := base*result + dgtDgts[i]; |
|||
//this is th reason for speed up.Hide the waiting for reading of dgtDgts[i] |
|||
tmpDgt := dgtDgts[i]; |
|||
result *= base; |
|||
dec(i); |
|||
result +=tmpDgt; |
|||
until (i< 0); |
|||
end; |
|||
end; |
end; |
||
procedure IncMAXBASEDigits(var dgt:tDigits); |
|||
function CntPrimeInBases(n:Uint64;max:Int32):Uint32; |
|||
var |
|||
i,q,tmp :NativeInt; |
|||
Begin |
|||
with dgt do |
|||
Begin |
|||
tmp := dgtMaxIdx; |
|||
i := 0; |
|||
repeat |
|||
q := dgtDgts[i]+1; |
|||
q -= (-ORD(q >=MAXBASE) AND MAXBASE); |
|||
dgtDgts[i] := q; |
|||
inc(i); |
|||
until q <> 0; |
|||
dec(i); |
|||
if tmp < i then |
|||
begin |
|||
tmp := i; |
|||
dgtMaxIdx := i; |
|||
end; |
|||
i := tmp; |
|||
repeat |
|||
tmp := dgtDgts[i]; |
|||
if q< tmp then |
|||
q := tmp; |
|||
dec(i); |
|||
until i <0; |
|||
dgtMaxDgtVal := q; |
|||
end; |
|||
end; |
|||
function CntPrimeInBases(var Digits :tdigits;max:Int32):Uint32; |
|||
var |
var |
||
Digits :tdigits; |
|||
pr : Uint64; |
pr : Uint64; |
||
base |
base: Uint32; |
||
begin |
begin |
||
result := 0; |
result := 0; |
||
IncMAXBASEDigits(Digits); |
|||
Base := Digits.dgtMaxDgtVal+1; |
|||
IF Digits[0] = 0 then |
|||
//divisible by every base |
|||
IF Digits.dgtDgts[0] = 0 then |
|||
EXIT; |
EXIT; |
||
if base < MinBase then |
|||
base := MinBase; |
|||
// if (MAXBASE - Base) <= (max-result) then BREAK; |
// if (MAXBASE - Base) <= (max-result) then BREAK; |
||
max := (max+Base-MAXBASE); |
max := (max+Base-MAXBASE); |
||
if (max>=0) then |
if (max>=0) then |
||
EXIT; |
EXIT; |
||
for base := base TO MAXBASE do |
|||
dgtCnt := MAXDIGITCOUNT-1; |
|||
while (dgtCnt>0) AND (Digits[dgtCnt]= 0) do |
|||
dec(dgtCnt); |
|||
result := Ord(boolprimes[n]); |
|||
for base := base TO MAXBASE-1 do |
|||
begin |
begin |
||
pr := CnvtoBase(Digits,base |
pr := CnvtoBase(Digits,base); |
||
inc(result,Ord(boolprimes[pr])); |
inc(result,Ord(boolprimes[pr])); |
||
//no chance to reach max then exit |
//no chance to reach max then exit |
||
if result< |
if result<max then |
||
break; |
break; |
||
inc(max); |
inc(max); |
||
end; |
end; |
||
end; |
end; |
||
function GetMaxBaseCnt(MinLmt,MaxLmt:Uint32):tSol; |
function GetMaxBaseCnt(var dgt:tDigits;MinLmt,MaxLmt:Uint32):tSol; |
||
var |
var |
||
i : Uint32; |
i : Uint32; |
||
Line 815: | Line 884: | ||
For i := MinLmt to MaxLmt do |
For i := MinLmt to MaxLmt do |
||
Begin |
Begin |
||
baseCnt := CntPrimeInBases( |
baseCnt := CntPrimeInBases(dgt,max); |
||
if baseCnt = 0 then |
if baseCnt = 0 then |
||
continue; |
continue; |
||
Line 840: | Line 909: | ||
function Out_String(n:Uint64;var s: AnsiString):Uint32; |
function Out_String(n:Uint64;var s: AnsiString):Uint32; |
||
//out-sourced for debugging purpose |
//out-sourced for debugging purpose |
||
const |
|||
CharOfBase= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'; |
|||
var |
var |
||
dgt:tDigits; |
dgt:tDigits; |
||
Line 848: | Line 915: | ||
Begin |
Begin |
||
result := 0; |
result := 0; |
||
CnvtoMAXBASE(n,dgt); |
|||
sl := ''; |
sl := ''; |
||
with dgt do |
|||
i := MaxDgtPos; |
|||
begin |
|||
while (i>=0)do |
|||
base:= dgtMaxDgtVal+1; |
|||
Begin |
|||
i := dgtMaxIdx; |
|||
while (i>=0)do |
|||
Begin |
|||
sl += CharOfBase[dgtDgts[i]+1]; |
|||
dec(i); |
|||
end; |
|||
s := sl+' -> ['; |
|||
end; |
end; |
||
s := sl+' -> ['; |
|||
For base := base to MAXBASE do |
For base := base to MAXBASE do |
||
if boolprimes[CnvtoBase(dgt,base |
if boolprimes[CnvtoBase(dgt,base)] then |
||
begin |
begin |
||
inc(result); |
inc(result); |
||
Line 887: | Line 957: | ||
var |
var |
||
dgt:tDigits; |
|||
T0 : Int64; |
T0 : Int64; |
||
i : NativeInt; |
|||
lmt,minLmt : UInt32; |
lmt,minLmt : UInt32; |
||
i : Uint32; |
|||
begin |
begin |
||
T0 := GetTickCount64; |
T0 := GetTickCount64; |
||
Line 896: | Line 968: | ||
for i := 1 to MAXDIGITCOUNT do |
for i := 1 to MAXDIGITCOUNT do |
||
lmt :=lmt*MAXBASE+MAXBASE-1; |
lmt :=lmt*MAXBASE+MAXBASE-1; |
||
writeln('max prime limit ',lmt); |
writeln('max prime limit ',lmt); |
||
Sieve(lmt); |
Sieve(lmt); |
||
writeln('Prime sieving ',(GetTickCount64-T0)/1000:6:3,' s'); |
writeln('Prime sieving ',(GetTickCount64-T0)/1000:6:3,' s'); |
||
CnvtoMAXBASE(0,dgt); |
|||
T0 := GetTickCount64; |
T0 := GetTickCount64; |
||
i := 1; |
i := 1; |
||
Line 904: | Line 978: | ||
repeat |
repeat |
||
write(i:2,' character strings which are prime in count bases = '); |
write(i:2,' character strings which are prime in count bases = '); |
||
Out_Sol(GetMaxBaseCnt(minLmt,MAXBASE*minLmt-1)); |
Out_Sol(GetMaxBaseCnt(dgt,minLmt,MAXBASE*minLmt-1)); |
||
minLmt *= MAXBASE; |
minLmt *= MAXBASE; |
||
inc(i); |
inc(i); |
||
until i>MAXDIGITCOUNT; |
until i>MAXDIGITCOUNT; |
||
writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s'); |
writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s'); |
||
{$IFDEF WINDOWS} readln; {$ENDIF} |
{$IFDEF WINDOWS} readln; {$ENDIF} |
||
end.</lang> |
end.</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
//at home 2200G 16GB Linux |
|||
TIO.RUN// extreme volatile timings for sieving primes |
|||
max prime limit 916132831 |
|||
Prime sieving 3.788 s |
|||
1 character strings which are prime in count bases = 60 |
|||
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62] |
|||
2 character strings which are prime in count bases = 31 |
|||
65 -> [7,8,9,11,13,14,16,17,18,21,22,24,27,28,29,31,32,37,38,39,41,42,43,44,46,48,51,52,57,58,59] |
|||
3 character strings which are prime in count bases = 33 |
|||
1L1 -> [22,23,25,26,27,28,29,30,31,32,33,34,36,38,39,40,41,42,43,44,45,46,48,51,52,53,54,57,58,59,60,61,62] |
|||
B9B -> [13,14,15,16,17,19,20,21,23,24,26,27,28,30,31,34,36,39,40,42,45,47,49,50,52,53,54,57,58,59,60,61,62] |
|||
4 character strings which are prime in count bases = 32 |
|||
1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36,37,38,39,41,45,46,48,50,51,57,58,60,61] |
|||
417B -> [12,13,15,16,17,18,19,21,23,25,28,30,32,34,35,37,38,39,41,45,48,49,50,51,52,54,56,57,58,59,61,62] |
|||
5 character strings which are prime in count bases = 30 |
|||
50161 -> [7,8,9,13,17,18,19,20,25,28,29,30,31,33,35,36,38,39,41,42,43,44,47,48,52,55,56,59,60,62] |
|||
Converting 12.738 s |
|||
Real time: 16.768 s User time: 16.128 s Sys. time: 0.488 s CPU share: 99.09 % |
|||
//at home AMD 2200G Linux fpc 3.2.2 |
|||
real 0m8,609s user 0m8,378s sys 0m0,220s |
|||
max prime limit 916132831 |
|||
Prime sieving 1.734 s |
|||
Converting 6.842 s |
|||
//base = 36 maxcharacters = 6 |
//base = 36 maxcharacters = 6 |
||
max prime limit 2176782335 |
max prime limit 2176782335 |
||
Prime sieving |
Prime sieving 4.986 s |
||
1 character strings which are prime in count bases = 34 |
1 character strings which are prime in count bases = 34 |
||
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36] |
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36] |
||
Line 938: | Line 1,040: | ||
441431 -> [5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33] |
441431 -> [5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33] |
||
Converting |
Converting 15.507 s// 24.3s before |
||
real 0m29,389s |
|||
###################### |
|||
TIO.RUN// extreme volatile timings for sieving primes |
|||
Maxbase = 62 maxcharacters = 5 |
|||
max prime limit 916132831 |
|||
Prime sieving 14.576 s |
|||
1 character strings which are prime in count bases = 60 |
|||
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62] |
|||
2 character strings which are prime in count bases = 31 |
|||
65 -> [7,8,9,11,13,14,16,17,18,21,22,24,27,28,29,31,32,37,38,39,41,42,43,44,46,48,51,52,57,58,59] |
|||
3 character strings which are prime in count bases = 33 |
|||
1L1 -> [22,23,25,26,27,28,29,30,31,32,33,34,36,38,39,40,41,42,43,44,45,46,48,51,52,53,54,57,58,59,60,61,62] |
|||
B9B -> [13,14,15,16,17,19,20,21,23,24,26,27,28,30,31,34,36,39,40,42,45,47,49,50,52,53,54,57,58,59,60,61,62] |
|||
4 character strings which are prime in count bases = 32 |
|||
1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36,37,38,39,41,45,46,48,50,51,57,58,60,61] |
|||
417B -> [12,13,15,16,17,18,19,21,23,25,28,30,32,34,35,37,38,39,41,45,48,49,50,51,52,54,56,57,58,59,61,62] |
|||
5 character strings which are prime in count bases = 30 |
|||
50161 -> [7,8,9,13,17,18,19,20,25,28,29,30,31,33,35,36,38,39,41,42,43,44,47,48,52,55,56,59,60,62] |
|||
real 0m20,566s</pre> |
|||
Converting 19.044 s |
|||
Real time: 33.929 s User time: 24.091 s Sys. time: 9.093 s CPU share: 97.80 % |
|||
//at home real 0m12,614s user 0m12,336s sys 0m0,238s |
|||
</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |