Anonymous user
Giuga numbers: Difference between revisions
m
→alternative version: limit count of search factors to 7 and other small optimizations
(→{{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:
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;
{
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}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$COPERATORS ON}
Line 510 ⟶ 523:
;
const
LMT = 24423128562;//24423128562;//2214408306;//432749205173838
type
tFac = packed record
Line 517 ⟶ 530:
fPrimIdx :Uint32;
end;
tFacs = array[0..
tPrimes = array[0..
// tPrimes = array[0..
// tPrimes = array[0..
var
SmallPrimes: tPrimes;
T0 : Int64;
cnt:Uint32;
procedure InitSmallPrimes;
//get primes.
const
MAXLIMIT = 775807 DIV 2+1;//(trunc(sqrt(LMT)+1)-1) shr 1+4;
var
pr : array of byte;
Line 570 ⟶ 584:
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
setlength(pr,0);
end;
Line 606 ⟶ 618:
procedure InsertNextPrimeFac(var F:tFacs;idx:Uint32);
var
i,p : uint32;
begin
begin
Mul := fMul;
i := fPrimIdx+1;
end;
if i<High(SmallPrimes) then
repeat
Line 614 ⟶ 631:
begin
p := SmallPrimes[i];
fPrimIdx := i;▼
fPrime := p;
if fMul>LMT then▼
BREAK;
IF (Mul-1) MOD p = 0 then
IF ChkGiuga(F,idx) then
OutFac(F,idx);
end;
// max 7 factors [0..6]
InsertNextPrimeFac(F,idx+1);▼
▲ InsertNextPrimeFac(F,idx+1);
inc(i);
until i>High(SmallPrimes);
Line 644 ⟶ 662:
fMul := 2*3;fPrime := 3;fPrimIdx:= 1;
end;
InsertNextPrimeFac(Facs,2);
Line 650 ⟶ 667:
writeln('Found ',cnt);
writeln;
end.
</lang>
{{out|@TIO.RUN}}
<pre>
1 2*3*5 = 30 0.000 s
2 2*3*7*41 = 1722
3 2*3*7*43*3041*4447 = 24423128562
4 2*3*11*13 = 858
5 2*3*11*17*59 = 66198
6 2*3*11*23*31*47057 = 2214408306
Found 6
Real time:
//@home real
</pre>
| |||