Giuga numbers: Difference between revisions
Content added Content deleted
(Giuga numbers in Python) |
(→{{header|Perl}}: prepend Pascal brute force) |
||
Line 134: | Line 134: | ||
</pre> |
</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}}== |
=={{header|Perl}}== |
||
<lang perl>#!/usr/bin/perl |
<lang perl>#!/usr/bin/perl |