Rosetta Code

Giuga numbers: Difference between revisions

Page Discussion

Giuga numbers (view source)

Revision as of 06:53, 7 July 2022

550 bytes removed ,  1 year ago
m
→‎{{header|Free Pascal}}: simplifiying, no performance improvement.
(Added C++ solution)
m (→‎{{header|Free Pascal}}: simplifiying, no performance improvement.)
Line 265:
;
//######################################################################
//prime decomposition only squarefree and multiple of 6
 
type
tprimeFac = packed record
pfRemain pfpotPrimIdx : array[0..9] of Uint64;
pfMaxIdx : Uint32;
pfpotPrimIdx : array[0..9] of Uint32;▼
end;
tpPrimeFac = ^tprimeFac;
tPrimes = array[0..65535] of Uint32;
 
var
{$ALIGN 8}
SmallPrimes: tPrimes;
{$ALIGN 32}
 
procedure InitSmallPrimes;
//get primes. #0..65535.Sieving only odd numbers
Line 305 ⟶ 304:
until j>MAXLIMIT;
until false;
 
SmallPrimes[1] := 3;
SmallPrimes[2] := 5;
Line 323 ⟶ 322:
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
end;
 
function OutPots(pD:tpPrimeFac;n:NativeInt):Ansistring;
var
Line 342 ⟶ 341:
str(p,s);
result += s;
end;▼
p := pfRemain;
If p >1 then▼
Begin
str(p,s);▼
chk *= p;▼
result += '*'+s;
end;
str(chk,s);
Line 354 ⟶ 346:
end;
end;
 
function IsSquarefreeDecompIsSquarefreeDecomp6(var res:tPrimeFac;n:Uint64):boolean;inline;
//factorize only not prime/semiprime and squarefree n= n div 6
var
pr,i,q,idx :NativeUInt;
Begin
with res do
Begin
pfMaxIdxIdx := 02;
 
q := n DIV 2;▼
if n = 2*q then▼
Begin
pfpotPrimIdx[pfMaxIdx] := 2;▼
n := q;
if (q AND 1) = 0 then
EXIT(false);
inc(pfMaxIdx);▼
end;▼
 
q := n DIV 3;▼
if n = 3*q then
Begin
pfpotPrimIdx[pfMaxIdx] := 3;▼
n := q;▼
q := q div 3;
if n = 3*q then
EXIT(false);
inc(pfMaxIdx);▼
end;
 
q := n DIV 5;
if n = 5*q then
Begin
pfpotPrimIdx[pfMaxIdx2] := 5;
n := q;
q := q div 5;
if q*5=n then
EXIT(false);
inc(pfMaxIdxIdx);
end;
 
Line 399 ⟶ 370:
if n = 7*q then
Begin
pfpotPrimIdx[pfMaxIdxIdx] := 7;
n := q;
q := q div 7;
if q*7=n then
EXIT(false);
inc(pfMaxIdxIdx);
end;
 
Line 410 ⟶ 381:
if n = 11*q then
Begin
pfpotPrimIdx[pfMaxIdxIdx] := 11;
n := q;
q := q div 11;
if q*11=n then
EXIT(false);
inc(pfMaxIdxIdx);
end;
 
if pfMaxIdxIdx < 3 then
Exit(false);
 
i := 5;
while i < High(SmallPrimes) do
begin
Line 431 ⟶ 402:
if n = pr*q then
Begin
pfpotPrimIdx[pfMaxIdxIdx] := pr;
n := q;
q := n div pr;
if pr*q = n then
EXIT(false);
inc(pfMaxIdxIdx);
end;
inc(i);
end;
▲ If pif n <> 1 then
pfRemain := n;begin
▲ pfpotPrimIdx : array[0..9Idx] of:= Uint32n;
▲ str inc(p,sIdx);
▲ end;
▲ inc(pfMaxIdx) := idx;
end;
exit(true);
Line 448 ⟶ 423:
function ChkGiuga(n:Uint64;pPrimeDecomp :tpPrimeFac):boolean;inline;
var
pFrp : Uint64;
idx: NativeInt;
p : Uint32;
begin
with pPrimeDecomp^ do
Begin
pfR idx := pfRemainpfMaxIdx-1;
idx := pfMaxIdx;
if pfR <> 1 then
begin
if sqr(pfR)>=n then
EXIT(false);
//squarefree
result := (((n DIV pfR)-1)MOD pfR) = 0;
if result then
begin
idx -= 1;▼
repeat
p := pfpotPrimIdx[idx];
result := (((n DIV p)-1)MOD p) = 0;
if Not(result) then
EXIT(result);
dec(idx);
until idx <0;
end;
end
else
begin
result := true;
repeat
dec(idx);
p := pfpotPrimIdx[idx];
result := (((n DIV p)-1)MOD p) = 0;
if not(result) then
EXIT(false);
until dec(idx<=0);
▲ until idx -= 1<0;
end;
end;
end;
 
const
LMT = 24423128562;//2214408306;//
Line 493 ⟶ 444:
PrimeDecomp :tPrimeFac;
T0:Int64;
n,n6 : NativeUIntUInt64;
cnt:Uint32;
Begin
InitSmallPrimes;
 
T0 := GetTickCount64;
with PrimeDecomp do
 
n := 6;begin
▲ pfpotPrimIdx[pfMaxIdx0] := 2;
▲ pfpotPrimIdx[pfMaxIdx1] := 3;
▲ end;
▲ qn := n DIV 20;
▲ qn6 := n DIV 30;
cnt := 0;
repeat
//only multibles of 6
inc(n,6);
▲ inc(pfMaxIdxn6);
//no square factor of 2
if IsSquarefreeDecomp(PrimeDecomp,n)then▼
if ChkGuiga(n,@PrimeDecomp) AND 3 = 0 then
▲ chk *= pcontinue;
//no square factor of 3
▲ if n MOD 9 = 2*q0 then
▲ n := qcontinue;
 
▲ if IsSquarefreeDecompIsSquarefreeDecomp6(PrimeDecomp,nn6)then
if ChkGiuga(n,@PrimeDecomp) then
begin
inc(cnt);
Line 519 ⟶ 482:
writeln(OutPots(@PrimeDecomp,n));
end.</lang>
{{out|@home AMD 5600G ( 4,4 Ghz ) fpc3.2.2 -O4 -Xs}
<pre>
1..30 : 8 : 2*3*5_chk_30< 0.000 s
2..858 : 1 : 2*3*11*13_chk_858< 0.000 s
3..1722 : 1 : 2*3*7*41_chk_1722< 0.000 s
4..66198 : 1 : 2*3*11*17*59_chk_66198< 0.000 s
5..2214408306 : 1 : 2*3*11*23*31*47057_chk_2214408306< 17.723120 s
6..24423128562 : 1 : 2*3*7*43*3041*4447_chk_24423128562< 457450.019180 s
Found 6
Tested til 24423128562 runtime 457450.019180 s
 
24423128562 :2*3*7*43*3041*4447_chk_24423128562
TIO.RUN (~2.3 Ghz )takes ~4x runtime ? ( 2214408306 DIV 2 ) in 36 secs :-(
</pre>
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/321425"