Rosetta Code

Multi-base primes: Difference between revisions

Page Discussion

Multi-base primes (view source)

Revision as of 05:05, 5 July 2021

149 bytes removed ,  2 years ago
m
→‎{{header|Pascal}}: check count of primes in base enpassant no need for big array BaseCnvCount (10 Mbyte for 6 digits )
m (→‎{{header|REXX}}: added the number of bases found for any maximums.)
m (→‎{{header|Pascal}}: check count of primes in base enpassant no need for big array BaseCnvCount (10 Mbyte for 6 digits ))
Line 455:
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
// //{$R+,O+}
{$ELSE}
{$APPTYPE CONSOLE}
Line 467:
MAXFAC = 10*10*10*10*10*10;//10*10*10*10*10*10*10*10*10;//
type
tdigits = array [0..15] of byte;//must be 0..15
tChkLst = array of byte;
tSol = array of Uint32;
//sieve primes see http://rosettacode.org/wiki/Sieve_of_Eratosthenes#alternative_using_wheel
var
BoolPrimes: array of boolean;
BaseCnvCount :tChkLst;
 
function BuildWheel(primeLimit:Int32):NativeUint;
Line 563 ⟶ 561:
function getDecDigitsAndMaxDgt(n:Uint32;var dgt:tDigits):uint32;
var
pQ :pQWord;
q,r,i: Uint32;
Begin
fillChar(pQ := @dgt[0],SizeOf(dgt),#;pQ[0] := 0;pQ[1] := 0);
//aka fillChar(dgt[0],SizeOf(dgt),#0);
i := 0;
result := 0;
Line 594:
end;
 
procedurefunction ConvertToBasesCntPrimeInBases(n:Uint32):Uint32;
var
Digits :tdigits;
base,minimalBase,Counter: Uint32;
begin
//base 10
Counterresult := Ord(boolprimes[n]);
//minimalBase <= max. digit +1
//this takes 0.012s out of 0.155s
minimalBasebase := getDecDigitsAndMaxDgt(n,Digits)+1;
if minimalBase < MinBase then
if base minimalBase :=< MinBase; then
base := MinBase;
 
for base := minimalBasebase TO 9 do
inc(counterresult,Ord(boolprimes[CnvtoBase(Digits,base)]));
for base := 11 TO MAXBASE do
inc(counterresult,Ord(boolprimes[CnvtoBase(Digits,base)]));
 
BaseCnvCount[n] := Counter;
end;
 
function GetMaxGetMaxBaseCnt(MinLmt,MaxLmt:Uint32):tSol;
var
i,pcbaseCnt,max,Idx: Int32;
Begin
setlength(result,0);
Line 623 ⟶ 622:
For i := MinLmt to MaxLmt do
Begin
pcbaseCnt := BaseCnvCount[CntPrimeInBases(i]);
if pcbaseCnt = 0 then
continue;
if max<=pcbaseCnt then
begin
if max = pcbaseCnt then
begin
inc(Idx);
Line 639 ⟶ 638:
Idx:= 1;
setlength(result,1);
result[Idx-10] := i;
max := pcbaseCnt;
end;
end;
Line 647 ⟶ 646:
 
function Out_String(n:Uint32;var s: AnsiString):Uint32;
//out-sourced for debugging purpose
var
dgt:tDigits;
Line 653:
Begin
result := 0;
minimalbase:= getDecDigitsAndMaxDgt(n,dgt)+1;▼
str(n:7,sl);
s := sl+' -> [';
▲ minimalbase:= getDecDigitsAndMaxDgt(n,dgt)+1;
For base := minimalbase to MAXBASE do
if boolprimes[CnvtoBase(dgt,base)] then
Line 695:
writeln('max prime limit ',lmt);
Sieve(lmt);
writewriteln('Prime sieving ',(GetTickCount64-T0)/1000:6:3,' s');▼
Setlength(BaseCnvCount,MAXFAC);
 
▲ write('Prime sieving ',(GetTickCount64-T0)/1000:6:3,' s');
T0 := GetTickCount64;
For i := High(BaseCnvCount) downto 2 do
ConvertToBases(i);
writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s');▼
writeln;
 
i := 1;
minLmt := 1;
repeat
write(i:2,' character strings which are prime in count bases = ');
Out_Sol(GetMaxGetMaxBaseCnt(minLmt,10*minLmt-1));
minLmt *= 10;
inc(i);
until minLmt >= MAXFAC;
▲ writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s');
{$IFDEF WINDOWS} readln; {$ENDIF}
end.</lang>
{{out}}
<pre>
TIO.RUN // extreme volatile timings ala Primefor sieving primes:today 7.7up sto 15.. 4,7s Converting nearly stable6s
max prime limit 559744029
Prime sieving 2.098 s Converting 0.368168 s
 
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]
Line 741 ⟶ 734:
441431 -> [5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33]
 
Converting 0.333 s
Real time: 2.658 s User time: 2.295 s Sys. time: 0.319 s CPU share: 98.31 %
//at home
//Prime sieving 1.072071 s Converting 0.181171 s</pre>
 
=={{header|Phix}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/313404"