Giuga numbers: Difference between revisions

Content added Content deleted
(→‎{{header|Free Pascal}}: added version that generates prime factorication and than check Giuga)
m (→‎alternative version: limit count of search factors to 7 and other small optimizations)
Line 500: Line 500:
2*3 are set fixed. 2*3*5 followed 2*3*7 than 2*3*11. Therefor the results are unsorted.
2*3 are set fixed. 2*3*5 followed 2*3*7 than 2*3*11. Therefor the results are unsorted.
<lang pascal>program Giuga;
<lang pascal>program Giuga;
{
30 = 2 * 3 * 5.
858 = 2 * 3 * 11 * 13.
1722 = 2 * 3 * 7 * 41.
66198 = 2 * 3 * 11 * 17 * 59.
2214408306 = 2 * 3 * 11 * 23 * 31 * 47057.
24423128562 = 2 * 3 * 7 * 43 * 3041 * 4447.
432749205173838 = 2 * 3 * 7 * 59 * 163 * 1381 * 775807.
14737133470010574 = 2 * 3 * 7 * 71 * 103 * 67213 * 713863.
550843391309130318 = 2 * 3 * 7 * 71 * 103 * 61559 * 29133437.
244197000982499715087866346 = 2 * 3 * 11 * 23 * 31 * 47137 * 28282147 * 3892535183.
554079914617070801288578559178 = 2 * 3 * 11 * 23 * 31 * 47059 * 2259696349 * 110725121051.
1910667181420507984555759916338506 = 2 * 3 * 7 * 43 * 1831 * 138683 * 2861051 * 1456230512169437. }
{$IFDEF FPC}
{$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$COPERATORS ON}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$COPERATORS ON}
Line 510: Line 523:
;
;
const
const
LMT = 24423128562;//24423128562;//2214408306;//
LMT = 24423128562;//24423128562;//2214408306;//432749205173838
type
type
tFac = packed record
tFac = packed record
Line 517: Line 530:
fPrimIdx :Uint32;
fPrimIdx :Uint32;
end;
end;
tFacs = array[0..31] of tFac;
tFacs = array[0..64] of tFac;
tPrimes = array[0..14379] of Uint32;
tPrimes = array[0..62157] of Uint32;//775807
// tPrimes = array[0..50847533] of Uint32;
// tPrimes = array[0..14379] of Uint32;//sqrt 24423128562
// tPrimes = array[0..5761454] of Uint32;
// tPrimes = array[0..1807414] of Uint32;//29133437
var
var
SmallPrimes: tPrimes;
SmallPrimes: tPrimes;
T0 : Int64;
T0 : Int64;
cnt:Uint32;
cnt:Uint32;

procedure InitSmallPrimes;
procedure InitSmallPrimes;
//get primes. #0..65535.Sieving only odd numbers
//get primes. Sieving only odd numbers
const
const
// MAXLIMIT = (100*1000*1000-1) shr 1;
//MAXLIMIT = (trunc(sqrt(LMT)+1)-1) shr 1+4;
MAXLIMIT = (trunc(sqrt(LMT)+1)-1) shr 1;
MAXLIMIT = 775807 DIV 2+1;//(trunc(sqrt(LMT)+1)-1) shr 1+4;
var
var
pr : array of byte;
pr : array of byte;
Line 570: Line 584:
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
setlength(pr,0);
setlength(pr,0);
writeln(p);
writeln(j);
end;
end;


Line 606: Line 618:
procedure InsertNextPrimeFac(var F:tFacs;idx:Uint32);
procedure InsertNextPrimeFac(var F:tFacs;idx:Uint32);
var
var
i,p,Mul : uint32;
Mul : Uint64;
i,p : uint32;
begin
begin
i := F[idx-1].fPrimIdx+1;
with F[idx-1] do
begin
Mul := fMul;
i := fPrimIdx+1;
end;
if i<High(SmallPrimes) then
if i<High(SmallPrimes) then
repeat
repeat
Line 614: Line 631:
begin
begin
p := SmallPrimes[i];
p := SmallPrimes[i];
⚫
fPrimIdx := i;
fPrime := p;
fPrime := p;
Mul := F[idx-1].fMul;
fPrimIdx := i;
fMul := Mul*p;
if p*Mul>LMT then
⚫
if fMul>LMT then
BREAK;
BREAK;
⚫
fMul := Mul*p;
IF (Mul-1) MOD p = 0 then
IF (Mul-1) MOD p = 0 then
IF ChkGiuga(F,idx) then
IF ChkGiuga(F,idx) then
OutFac(F,idx);
OutFac(F,idx);
end;
end;
// max 7 factors [0..6]
⚫
InsertNextPrimeFac(F,idx+1);
⚫
if idx <6 then
⚫
InsertNextPrimeFac(F,idx+1);
inc(i);
inc(i);
until i>High(SmallPrimes);
until i>High(SmallPrimes);
Line 644: Line 662:
fMul := 2*3;fPrime := 3;fPrimIdx:= 1;
fMul := 2*3;fPrime := 3;fPrimIdx:= 1;
end;
end;

InsertNextPrimeFac(Facs,2);
InsertNextPrimeFac(Facs,2);


Line 650: Line 667:
writeln('Found ',cnt);
writeln('Found ',cnt);
writeln;
writeln;
end.</lang>
end.
</lang>
{{out|@TIO.RUN}}
{{out|@TIO.RUN}}
<pre>
<pre>
78135 // limit of search prime
14380 // count of primes

1 2*3*5 = 30 0.000 s
1 2*3*5 = 30 0.000 s
2 2*3*7*41 = 1722 12.321 s
2 2*3*7*41 = 1722 1.921 s
3 2*3*7*43*3041*4447 = 24423128562 12.536 s
3 2*3*7*43*3041*4447 = 24423128562 1.954 s
4 2*3*11*13 = 858 14.444 s
4 2*3*11*13 = 858 2.527 s
5 2*3*11*17*59 = 66198 14.937 s
5 2*3*11*17*59 = 66198 2.588 s
6 2*3*11*23*31*47057 = 2214408306 15.326 s
6 2*3*11*23*31*47057 = 2214408306 2.645 s
Found 6
Found 6
Real time: 41.668 s CPU share: 99.30 %
Real time: 8.733 s CPU share: 99.45 %

//@home real 0m6,431s
//@home real 0m1,604s
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Giuga_numbers"