Anonymous user
Giuga numbers: Difference between revisions
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
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;▼
If p >1 then▼
str(p,s);▼
chk *= p;▼
end;
str(chk,s);
Line 354 ⟶ 346:
end;
end;
function
//factorize only not prime/semiprime and squarefree n= n div 6
var
pr,i,q,idx :NativeUInt;
Begin
with res do
Begin
q := n DIV 2;▼
if n = 2*q then▼
pfpotPrimIdx[pfMaxIdx] := 2;▼
inc(pfMaxIdx);▼
end;▼
q := n DIV 3;▼
pfpotPrimIdx[pfMaxIdx] := 3;▼
n := q;▼
inc(pfMaxIdx);▼
q := n DIV 5;
if n = 5*q then
Begin
pfpotPrimIdx[
n := q;
q := q div 5;
if q*5=n then
EXIT(false);
inc(
end;
Line 399 ⟶ 370:
if n = 7*q then
Begin
pfpotPrimIdx[
n := q;
q := q div 7;
if q*7=n then
EXIT(false);
inc(
end;
Line 410 ⟶ 381:
if n = 11*q then
Begin
pfpotPrimIdx[
n := q;
q := q div 11;
if q*11=n then
EXIT(false);
inc(
end;
if
Exit(false);
i := 5;
while i < High(SmallPrimes) do
begin
Line 431 ⟶ 402:
if n = pr*q then
Begin
pfpotPrimIdx[
n := q;
q := n div pr;
if pr*q = n then
EXIT(false);
inc(
end;
inc(i);
end;
▲ end;
end;
exit(true);
Line 448 ⟶ 423:
function ChkGiuga(n:Uint64;pPrimeDecomp :tpPrimeFac):boolean;inline;
var
idx: NativeInt;
begin
idx -= 1;▼
repeat
p := pfpotPrimIdx[idx];
result := (((n DIV p)-1)MOD p) = 0;
if not(result) then
EXIT
end;
end;
const
LMT = 24423128562;//2214408306;//
Line 493 ⟶ 444:
PrimeDecomp :tPrimeFac;
T0:Int64;
n,n6 :
cnt:Uint32;
Begin
InitSmallPrimes;
T0 := GetTickCount64;
with PrimeDecomp do
cnt := 0;
repeat
//only multibles of 6
inc(n,6);
//no square factor of 2
if IsSquarefreeDecomp(PrimeDecomp,n)then▼
//no square factor of 3
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 :
2..858 :
3..1722 :
4..66198 :
5..2214408306 :
6..24423128562 :
Found 6
Tested til 24423128562 runtime
24423128562 :2*3*7*43*3041*4447_chk_24423128562
TIO.RUN (~2.3 Ghz )takes ~4x runtime ? ( 2214408306 DIV 2 ) in 36 secs :-(
</pre>
|