124 lines
2.3 KiB
ObjectPascal
124 lines
2.3 KiB
ObjectPascal
program Untouchable_numbers;
|
|
|
|
{$APPTYPE CONSOLE}
|
|
|
|
uses
|
|
System.SysUtils;
|
|
|
|
function SumDivisors(n: Integer): Integer;
|
|
begin
|
|
Result := 1;
|
|
var k := 2;
|
|
if not odd(n) then
|
|
k := 1;
|
|
var i := 1 + k;
|
|
while i * i <= n do
|
|
begin
|
|
if (n mod i) = 0 then
|
|
begin
|
|
inc(Result, i);
|
|
var j := n div i;
|
|
if j <> i then
|
|
inc(Result, j);
|
|
end;
|
|
inc(i, k);
|
|
end;
|
|
end;
|
|
|
|
function Sieve(n: Integer): TArray<Boolean>;
|
|
begin
|
|
inc(n);
|
|
SetLength(result, n + 1);
|
|
for var i := 6 to n do
|
|
begin
|
|
var sd := SumDivisors(i);
|
|
if sd <= n then
|
|
result[sd] := True;
|
|
end;
|
|
end;
|
|
|
|
function PrimeSieve(limit: Integer): TArray<Boolean>;
|
|
begin
|
|
inc(limit);
|
|
SetLength(result, limit);
|
|
Result[0] := True;
|
|
Result[1] := True;
|
|
|
|
var p := 3;
|
|
repeat
|
|
var p2 := p * p;
|
|
if p2 >= limit then
|
|
Break;
|
|
var i := p2;
|
|
while i < limit do
|
|
begin
|
|
|
|
Result[i] := True;
|
|
inc(i, 2 * p);
|
|
end;
|
|
|
|
repeat
|
|
inc(p, 2);
|
|
until not Result[p];
|
|
|
|
until (False);
|
|
|
|
end;
|
|
|
|
function Commatize(n: Double): string;
|
|
var
|
|
fmt: TFormatSettings;
|
|
begin
|
|
fmt := TFormatSettings.Create('en-US');
|
|
Result := n.ToString(ffNumber, 64, 0, fmt);
|
|
end;
|
|
|
|
begin
|
|
var limit := 1000000;
|
|
var c := primeSieve(limit);
|
|
var s := sieve(63 * limit);
|
|
var untouchable: TArray<Integer> := [2, 5];
|
|
var n := 6;
|
|
while n <= limit do
|
|
begin
|
|
if not s[n] and c[n - 1] and c[n - 3] then
|
|
begin
|
|
SetLength(untouchable, Length(untouchable) + 1);
|
|
untouchable[High(untouchable)] := n;
|
|
end;
|
|
inc(n, 2);
|
|
end;
|
|
writeln('List of untouchable numbers <= 2,000:');
|
|
var count := 0;
|
|
var i := 0;
|
|
while untouchable[i] <= 2000 do
|
|
begin
|
|
write(commatize(untouchable[i]): 6);
|
|
if ((i + 1) mod 10) = 0 then
|
|
writeln;
|
|
inc(i);
|
|
end;
|
|
writeln(#10#10, commatize(count): 7, ' untouchable numbers were found <= 2,000');
|
|
|
|
var p := 10;
|
|
count := 0;
|
|
for n in untouchable do
|
|
begin
|
|
inc(count);
|
|
if n > p then
|
|
begin
|
|
var cc := commatize(count - 1);
|
|
var cp := commatize(p);
|
|
writeln(cc, ' untouchable numbers were found <= ', cp);
|
|
p := p * 10;
|
|
if p = limit then
|
|
Break;
|
|
end;
|
|
end;
|
|
|
|
var cu := commatize(Length(untouchable));
|
|
var cl := commatize(limit);
|
|
writeln(cu:7, ' untouchable numbers were found <= ', cl);
|
|
readln;
|
|
end.
|