Anonymous user
Giuga numbers: Difference between revisions
→{{header|Perl}}: prepend Pascal brute force
(Giuga numbers in Python) |
(→{{header|Perl}}: prepend Pascal brute force) |
||
Line 134:
</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
changing main routine at the end of [[Factors_of_an_integer#using_Prime_decomposition]]
<lang>
const
LMT = 24423128562;//70*1000;//
var
pPrimeDecomp :tpPrimeFac;
T0:Int64;
n : NativeUInt;
idx,p,cnt : Int32;
chk: boolean;
BEGIN
InitSmallPrimes;
T0 := GetTickCount64;
n := 1;
Init_Sieve(n);
pPrimeDecomp:= GetNextPrimeDecomp;
cnt := 0;
repeat
inc(n);
pPrimeDecomp:= GetNextPrimeDecomp;
with pPrimeDecomp^ do
begin
//if prime/semi-prime
if pfDivCnt <= 4 then continue;
//not even
if pfpotPrimIdx[0] <> 0 then continue;
idx := pfMaxIdx;//always>0 for pfDivcnt>2
if pfRemain = 1 then
begin
//not squarefree or biggest prime factor to big
if ((1 shl idx) <> pfdivcnt) or (sqr(SmallPrimes[pfpotPrimIdx[idx-1]])>=n) then
continue;
//check for Giuga number
chk := true;
For idx := idx-1 downto 0 do
begin
p := SmallPrimes[pfpotPrimIdx[idx]];
chk := (((n DIV p)-1)MOD p) = 0;
if not(chk) then
BREAK;
end;
end
else
begin
if (1 shl (idx+1) <> pfdivcnt) or (sqr(pfRemain)>=n) then
continue;
chk := (((n DIV pfRemain)-1)MOD pfRemain) = 0;
if chk then
For idx := idx-1 downto 0 do
begin
p := SmallPrimes[pfpotPrimIdx[idx]];
chk := (((n DIV p)-1)MOD p) = 0;
if not(chk) then
BREAK;
end;
end;
if chk then
begin
inc(cnt);
writeln(cnt:3,'..',OutPots(pPrimeDecomp,n));
end;
end;
until n >= LMT;
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
writeln('Count ',cnt);
writeln;
END.</lang>
{{out}}
<pre>
1..30 : 8 : 2*3*5_chk_30<_SoD_72<
2..858 : 16 : 2*3*11*13_chk_858<_SoD_2016<
3..1722 : 16 : 2*3*7*41_chk_1722<_SoD_4032<
4..66198 : 32 : 2*3*11*17*59_chk_66198<_SoD_155520<
5..2214408306 : 64 : 2*3*11*23*31*47057_chk_2214408306<_SoD_5204238336<
6..24423128562 : 64 : 2*3*7*43*3041*4447_chk_24423128562<_SoD_57154166784<
runtime 673.643 s
Count 6
real 11m13,645s user 11m12,962s sys 0m0,247s</pre>
=={{header|Perl}}==
<lang perl>#!/usr/bin/perl
| |||