Multi-base primes: Difference between revisions
Content added Content deleted
(Realize in F#) |
m (→{{header|Pascal}}: small improvement using digits getDecDigitsAndMaxDgt like Julia->Rust->Phix etc...) |
||
Line 455: | Line 455: | ||
{$MODE DELPHI} |
{$MODE DELPHI} |
||
{$OPTIMIZATION ON,ALL} |
{$OPTIMIZATION ON,ALL} |
||
// {$R+,O+} |
|||
{$CodeAlign proc=32,loop=1} |
|||
{$ELSE} |
{$ELSE} |
||
{$APPTYPE CONSOLE} |
{$APPTYPE CONSOLE} |
||
Line 463: | Line 463: | ||
const |
const |
||
MINBASE = 2; |
MINBASE = 2; |
||
MAXBASE = 36; |
MAXBASE = 36;//10;//10 is minimum |
||
MAXDIGITCOUNT = 6;//9;// |
|||
MAXFAC = 10*10*10*10*10*10; |
MAXFAC = 10*10*10*10*10*10;//10*10*10*10*10*10*10*10*10;// |
||
type |
type |
||
tdigits = array [0..15] of byte; |
|||
tChkLst = array of byte; |
tChkLst = array of byte; |
||
tSol = array of Uint32; |
tSol = array of Uint32; |
||
Line 472: | Line 473: | ||
var |
var |
||
BoolPrimes: array of boolean; |
BoolPrimes: array of boolean; |
||
BaseCnvCount :tChkLst; |
|||
function popcnt64(n:Uint64):integer; |
|||
begin |
|||
result := 0; |
|||
repeat |
|||
result += ORD(n AND 1 <> 0); |
|||
n := n shr 1; |
|||
until n = 0; |
|||
end; |
|||
function BuildWheel(primeLimit:Int32):NativeUint; |
function BuildWheel(primeLimit:Int32):NativeUint; |
||
Line 539: | Line 531: | ||
myPrimes[1] := false; |
myPrimes[1] := false; |
||
BuildWheel := pr+1; |
BuildWheel := pr+1; |
||
writeln; |
|||
end; |
end; |
||
Line 570: | Line 561: | ||
end; |
end; |
||
function |
function getDecDigitsAndMaxDgt(n:Uint32;var dgt:tDigits):uint32; |
||
//with test of digit >= base |
|||
var |
var |
||
q,r, |
q,r,i: Uint32; |
||
Begin |
Begin |
||
fillChar(dgt[0],SizeOf(dgt),#0); |
|||
fac := 1; |
|||
i := 0; |
|||
result := 0; |
result := 0; |
||
repeat |
repeat |
||
q := n DIV 10; |
q := n DIV 10; |
||
r := (n-q*10); |
r := (n-q*10); |
||
if r >= base then |
|||
break; |
|||
result += fac*r; |
|||
fac *= base; |
|||
n := q; |
n := q; |
||
dgt[i] := r; |
|||
inc(i); |
|||
result |
if result < r then |
||
result := r; |
|||
until n = 0; |
|||
end; |
end; |
||
function |
function CnvtoBase(const dgt:tDigits;base:Uint32):Uint32; |
||
var |
var |
||
i: Int32; |
|||
Begin |
Begin |
||
i := MAXDIGITCOUNT; |
|||
while (dgt[i] = 0) AND (i>0) do |
|||
dec(i); |
|||
result := 0; |
result := 0; |
||
repeat |
repeat |
||
result := base*result+dgt[i]; |
|||
dec(i); |
|||
until (i< 0); |
|||
result += fac*r; |
|||
fac *= Base; |
|||
n := q; |
|||
until n = 0; |
|||
end; |
end; |
||
procedure ConvertToBases(n:Uint32); |
procedure ConvertToBases(n:Uint32); |
||
var |
var |
||
Digits :tdigits; |
|||
base,r,Counter: Uint32; |
|||
base,minimalBase,Counter: Uint32; |
|||
begin |
begin |
||
Counter := 0; |
|||
//base 10 |
//base 10 |
||
Counter := Ord(boolprimes[n]); |
|||
//minimalBase <= max. digit +1 |
|||
inc(Counter); |
|||
minimalBase := getDecDigitsAndMaxDgt(n,Digits)+1; |
|||
for base := MINBASE TO 9 do |
|||
if minimalBase < MinBase then |
|||
Begin |
|||
minimalBase := MinBase; |
|||
// if boolprimes[r] then inc(Counter); |
|||
inc(Counter,Ord(boolprimes[r])); |
|||
end; |
|||
for base := minimalBase TO 9 do |
|||
inc(counter,Ord(boolprimes[CnvtoBase(Digits,base)])); |
|||
for base := 11 TO MAXBASE do |
for base := 11 TO MAXBASE do |
||
inc(counter,Ord(boolprimes[CnvtoBase(Digits,base)])); |
|||
Begin |
|||
r := CnvtoBase11toMAXBASE(n,base); |
|||
BaseCnvCount[n] := Counter; |
|||
inc(Counter,Ord(boolprimes[r])); |
|||
end; |
|||
chklst[n] := Counter; |
|||
end; |
end; |
||
Line 633: | Line 618: | ||
i,pc,max,Idx: Int32; |
i,pc,max,Idx: Int32; |
||
Begin |
Begin |
||
setlength(result, |
setlength(result,0); |
||
max :=-1; |
max :=-1; |
||
Idx:= 0; |
Idx:= 0; |
||
For i := MinLmt to MaxLmt do |
For i := MinLmt to MaxLmt do |
||
Begin |
Begin |
||
pc := |
pc := BaseCnvCount[i]; |
||
if pc= 0 then |
|||
continue; |
|||
if max<=pc then |
if max<=pc then |
||
begin |
begin |
||
Line 645: | Line 632: | ||
inc(Idx); |
inc(Idx); |
||
if Idx > High(result) then |
if Idx > High(result) then |
||
setlength(result,Idx |
setlength(result,Idx); |
||
result[idx-1] := i; |
result[idx-1] := i; |
||
end |
end |
||
Line 651: | Line 638: | ||
begin |
begin |
||
Idx:= 1; |
Idx:= 1; |
||
setlength(result,1); |
|||
result[Idx-1] := i; |
result[Idx-1] := i; |
||
max := pc; |
max := pc; |
||
Line 656: | Line 644: | ||
end; |
end; |
||
end; |
end; |
||
setlength(result,idx); |
|||
end; |
end; |
||
function Out_String(n:Uint32;var s: AnsiString):Uint32; |
|||
procedure Out_Sol(sol:tSol); |
|||
var |
var |
||
dgt:tDigits; |
|||
sl : string[8]; |
sl : string[8]; |
||
base,minimalbase: Uint32; |
|||
Begin |
|||
result := 0; |
|||
minimalbase:= getDecDigitsAndMaxDgt(n,dgt)+1; |
|||
str(n:7,sl); |
|||
s := sl+' -> ['; |
|||
For base := minimalbase to MAXBASE do |
|||
if boolprimes[CnvtoBase(dgt,base)] then |
|||
begin |
|||
inc(result); |
|||
str(base,sl); |
|||
s := s+sl+','; |
|||
end; |
|||
s[length(s)] := ']'; |
|||
end; |
|||
procedure Out_Sol(sol:tSol); |
|||
var |
|||
s : AnsiString; |
s : AnsiString; |
||
i |
i,cnt : Int32; |
||
begin |
begin |
||
if length(Sol) = 0 then |
if length(Sol) = 0 then |
||
EXIT; |
EXIT; |
||
cnt := 0; |
|||
for i := 0 to High(Sol) do |
for i := 0 to High(Sol) do |
||
begin |
begin |
||
cnt := Out_String(sol[i],s); |
|||
str(n:7,sl); |
|||
s := sl+' -> ['; |
|||
For base := MINBASE to MAXBASE do |
|||
Begin |
|||
r := CnvtoBase(n,base); |
|||
if boolprimes[r] then |
|||
begin |
|||
inc(cnt); |
|||
str(base,sl); |
|||
s := s+sl+','; |
|||
end; |
|||
end; |
|||
s[length(s)] := ']'; |
|||
if i = 0 then |
if i = 0 then |
||
writeln(cnt); |
writeln(cnt); |
||
Line 691: | Line 683: | ||
setlength(Sol,0); |
setlength(Sol,0); |
||
end; |
end; |
||
var |
var |
||
T0 : Int64; |
T0 : Int64; |
||
Line 698: | Line 691: | ||
lmt := 0; |
lmt := 0; |
||
//maxvalue of "99...99" in Maxbase |
//maxvalue of "99...99" in Maxbase |
||
for i := 1 to |
for i := 1 to MAXDIGITCOUNT do |
||
lmt := (lmt*MAXBASE+9); |
lmt := (lmt*MAXBASE+9); |
||
writeln('max prime limit ',lmt); |
writeln('max prime limit ',lmt); |
||
Sieve(lmt); |
Sieve(lmt); |
||
Setlength( |
Setlength(BaseCnvCount,MAXFAC); |
||
writeln('Start ',(GetTickCount64-T0)/1000:6:3,' s'); |
|||
write('Prime sieving ',(GetTickCount64-T0)/1000:6:3,' s'); |
|||
For i := 2 to MAXFAC-1 do |
|||
T0 := GetTickCount64; |
|||
For i := High(BaseCnvCount) downto 2 do |
|||
ConvertToBases(i); |
ConvertToBases(i); |
||
writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s'); |
|||
writeln; |
|||
i := 1; |
i := 1; |
||
minLmt := 1; |
minLmt := 1; |
||
repeat |
repeat |
||
write(i:2,' character strings which are prime in |
write(i:2,' character strings which are prime in count bases = '); |
||
Out_Sol(GetMax(minLmt,10*minLmt-1)); |
Out_Sol(GetMax(minLmt,10*minLmt-1)); |
||
minLmt *= 10; |
minLmt *= 10; |
||
Line 719: | Line 716: | ||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
TIO.RUN // extreme volatile timings ala Prime sieving 7.7 s .. 4,7s Converting nearly stable |
|||
TIO.RUN |
|||
max prime limit 559744029 |
max prime limit 559744029 |
||
Prime sieving 2.098 s Converting 0.368 s |
|||
1 character strings which are prime in count bases = 34 |
|||
Start 2.343 s |
|||
1 character strings which are prime in most 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] |
||
2 character strings which are prime in |
2 character strings which are prime in count bases = 18 |
||
21 -> [3,5,6,8,9,11,14,15,18,20,21,23,26,29,30,33,35,36] |
21 -> [3,5,6,8,9,11,14,15,18,20,21,23,26,29,30,33,35,36] |
||
3 character strings which are prime in |
3 character strings which are prime in count bases = 18 |
||
131 -> [4,5,7,8,9,10,12,14,15,18,19,20,23,25,27,29,30,34] |
131 -> [4,5,7,8,9,10,12,14,15,18,19,20,23,25,27,29,30,34] |
||
551 -> [6,7,11,13,14,15,16,17,19,21,22,24,25,26,30,32,35,36] |
551 -> [6,7,11,13,14,15,16,17,19,21,22,24,25,26,30,32,35,36] |
||
737 -> [8,9,11,12,13,15,16,17,19,22,23,24,25,26,29,30,31,36] |
737 -> [8,9,11,12,13,15,16,17,19,22,23,24,25,26,29,30,31,36] |
||
4 character strings which are prime in |
4 character strings which are prime in count bases = 19 |
||
1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36] |
1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36] |
||
5347 -> [8,9,10,11,12,13,16,18,19,22,24,25,26,30,31,32,33,34,36] |
5347 -> [8,9,10,11,12,13,16,18,19,22,24,25,26,30,31,32,33,34,36] |
||
5 character strings which are prime in |
5 character strings which are prime in count bases = 18 |
||
30271 -> [8,10,12,13,16,17,18,20,21,23,24,25,31,32,33,34,35,36] |
30271 -> [8,10,12,13,16,17,18,20,21,23,24,25,31,32,33,34,35,36] |
||
6 character strings which are prime in |
6 character strings which are prime in count bases = 18 |
||
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] |
||
Real time: |
Real time: 2.658 s User time: 2.295 s Sys. time: 0.319 s CPU share: 98.31 % |
||
//at home |
|||
//Start 1.077 s real 0m1,364s at home</pre> |
|||
//Prime sieving 1.072 s Converting 0.181 s</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |