Deceptive numbers: Difference between revisions
Content added Content deleted
m (→{{header|Free Pascal}}: only checking odd divisors halving timing) |
m (→{{header|Free Pascal}}: No multiple of 5 like Nigel mentioned) |
||
Line 115: | Line 115: | ||
==={{header|Free Pascal}}=== |
==={{header|Free Pascal}}=== |
||
Brute force, not using gmp. Runtime ~ n^2.<BR> |
Brute force, not using gmp. Runtime ~ n^2.<BR> |
||
Like Wren,et alias only checking odd divisors |
Like Wren,et alias only checking odd divisors, no multiple of 3<BR> |
||
Like Nigel said, no multiple of 5. |
|||
<lang pascal>program DeceptiveNumbers; |
<lang pascal>program DeceptiveNumbers; |
||
{$IfDef FPC} {$Optimization ON,ALL} {$ENDIF} |
{$IfDef FPC} {$Optimization ON,ALL} {$ENDIF} |
||
Line 130: | Line 131: | ||
tmyUint64 = array[0..Limit DIV RepInitLen+1] of Uint64; |
tmyUint64 = array[0..Limit DIV RepInitLen+1] of Uint64; |
||
var |
var |
||
{$Align 32} |
|||
K: tmyUint64; |
K: tmyUint64; |
||
{$Align 32} |
|||
MaxKIdx : Int32; |
MaxKIdx : Int32; |
||
Line 201: | Line 204: | ||
end; |
end; |
||
const |
|||
NextNotMulOF35 : array[0..7] of byte = (6,4,2,4,2,4,6,2); |
|||
var |
var |
||
i |
i,cnt,idx35 : UInt64; |
||
BEGIN |
BEGIN |
||
fillchar(K,SizeOF(K),#0); |
fillchar(K,SizeOF(K),#0); |
||
MaxKIdx:= 0; |
MaxKIdx:= 0; |
||
cnt := 0; |
cnt := 0; |
||
i := |
i := 1; |
||
idx35 := 0; |
|||
For j := 3 to (LIMIT-1) DIV 2 do |
|||
repeat |
|||
inc(i, |
inc(i,NextNotMulOF35[idx35]); |
||
IF i > LIMIT then |
|||
BREAK; |
|||
idx35 := (idx35+1) AND 7; |
|||
if isprime(i) then |
|||
continue; |
continue; |
||
ExtendRep(k,i-1); |
ExtendRep(k,i-1); |
||
Line 218: | Line 226: | ||
inc(cnt); |
inc(cnt); |
||
write(i:6,','); |
write(i:6,','); |
||
if cnt Mod 10 = 0 then |
if cnt Mod 10 = 0 then |
||
writeln; |
|||
end; |
end; |
||
until false; |
|||
{$IfDef Windows} |
{$IfDef Windows} |
||
readln; |
readln; |
||
Line 228: | Line 237: | ||
{{out|@TIO.RUN}} |
{{out|@TIO.RUN}} |
||
<pre> |
<pre> |
||
Real time: 1. |
Real time: 1.009 s User time: 0.971 s Sys. time: 0.033 s CPU share: 99.43 % |
||
91, 259, 451, 481, 703, 1729, 2821, 2981, 3367, 4141, |
91, 259, 451, 481, 703, 1729, 2821, 2981, 3367, 4141, |
||
4187, 5461, 6533, 6541, 6601, 7471, 7777, 8149, 8401, 8911, |
4187, 5461, 6533, 6541, 6601, 7471, 7777, 8149, 8401, 8911, |
||
Line 235: | Line 245: | ||
45527, 46657, 48433, 50851, 50881, 52633, 54913, 57181, 63139, 63973, |
45527, 46657, 48433, 50851, 50881, 52633, 54913, 57181, 63139, 63973, |
||
65311, 66991, 67861, 68101, 75361, 79003, 82513, 83119, 94139, 95161, |
65311, 66991, 67861, 68101, 75361, 79003, 82513, 83119, 94139, 95161, |
||
97273, 97681, |
97273, 97681,</pre> |
||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |