Anonymous user
Square-free integers: Difference between revisions
added pascal counting til 1e10
(Add Swift) |
(added pascal counting til 1e10) |
||
Line 1,265:
607926
</pre>
=={{header|Pascal}}==
{{works with|Free Pascal}}
As so often, marking/sieving multiples of square of primes to speed things up.
<lang pascal>program SquareFree;
{$IFDEF FPC}
{$MODE DELPHI}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
const
//needs 1e10 Byte = 10 Gb maybe someone got 128 Gb :-) nearly linear time
BigLimit = 10*1000*1000*1000;
TRILLION = 1000*1000*1000*1000;
primeLmt = trunc(sqrt(TRILLION+150));
var
primes : array of byte;
sieve : array of byte;
procedure initPrimes;
var
i,lmt,dp :NativeInt;
Begin
setlength(primes,80000);
setlength(sieve,primeLmt);
sieve[0] := 1;
sieve[1] := 1;
i := 2;
repeat
IF sieve[i] = 0 then
Begin
lmt:= i*i;
while lmt<primeLmt do
Begin
sieve[lmt] := 1;
inc(lmt,i);
end;
end;
inc(i);
until i*i>=primeLmt;
//extract difference of primes
i := 0;
lmt := 0;
dp := 0;
repeat
IF sieve[i] = 0 then
Begin
primes[lmt] := dp;
dp := 0;
inc(lmt);
end;
inc(dp);
inc(i);
until i >primeLmt;
setlength(sieve,0);
setlength(Primes,lmt+1);
end;
procedure SieveSquares;
//mark all powers >=2 of prime => all powers = 2 is sufficient
var
pSieve : pByte;
i,sq,k,prime : NativeInt;
Begin
pSieve := @sieve[0];
prime := 0;
For i := 0 to High(primes) do
Begin
prime := prime+primes[i];
sq := prime*prime;
k := sq;
if sq > BigLimit then
break;
repeat
pSieve[k] := 1;
inc(k,sq);
until k> BigLimit;
end;
end;
procedure Count_x10;
var
pSieve : pByte;
i,lmt,cnt: NativeInt;
begin
writeln(' square free count');
writeln('[1 to limit]');
pSieve := @sieve[0];
lmt := 10;
i := 1;
cnt := 0;
repeat
while i <= lmt do
Begin
inc(cnt,ORD(pSieve[i] = 0));
inc(i);
end;
writeln(lmt:12,' ',cnt:12);
IF lmt >= BigLimit then
BREAK;
lmt := lmt*10;
IF lmt >BigLimit then
lmt := BigLimit;
until false;
end;
function TestSquarefree(N:Uint64):boolean;
var
i,prime,sq : NativeUint;
Begin
prime := 0;
result := false;
For i := 0 to High(primes) do
Begin
prime := prime+primes[i];
sq := sqr(prime);
IF sq> N then
BREAK;
IF N MOD sq = 0 then
EXIT;
end;
result := true;
end;
var
i,k : NativeInt;
Begin
InitPrimes;
setlength(sieve,BigLimit+1);
SieveSquares;
writeln('Square free numbers from 1 to 145');
k := 80 div 4;
For i := 1 to 145 do
If sieve[i] = 0 then
Begin
write(i:4);
dec(k);
IF k = 0 then
Begin
writeln;
k := 80 div 4;
end;
end;
writeln;writeln;
writeln('Square free numbers from ',TRILLION,' to ',TRILLION+145);
k := 4;
For i := TRILLION to TRILLION+145 do
Begin
if TestSquarefree(i) then
Begin
write(i:20);
dec(k);
IF k = 0 then
Begin
writeln;
k := 4;
end;
end;
end;
writeln;writeln;
Count_x10;
end.</lang>
{{out}}
<pre style="height:35ex">Square free numbers from 1 to 145
1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31
33 34 35 37 38 39 41 42 43 46 47 51 53 55 57 58 59 61 62 65
66 67 69 70 71 73 74 77 78 79 82 83 85 86 87 89 91 93 94 95
97 101 102 103 105 106 107 109 110 111 113 114 115 118 119 122 123 127 129 130
131 133 134 137 138 139 141 142 143 145
Square free numbers from 1000000000000 to 1000000000145
1000000000001 1000000000002 1000000000003 1000000000005
1000000000006 1000000000007 1000000000009 1000000000011
1000000000013 1000000000014 1000000000015 1000000000018
1000000000019 1000000000021 1000000000022 1000000000023
1000000000027 1000000000029 1000000000030 1000000000031
1000000000033 1000000000037 1000000000038 1000000000039
1000000000041 1000000000042 1000000000043 1000000000045
1000000000046 1000000000047 1000000000049 1000000000051
1000000000054 1000000000055 1000000000057 1000000000058
1000000000059 1000000000061 1000000000063 1000000000065
1000000000066 1000000000067 1000000000069 1000000000070
1000000000073 1000000000074 1000000000077 1000000000078
1000000000079 1000000000081 1000000000082 1000000000085
1000000000086 1000000000087 1000000000090 1000000000091
1000000000093 1000000000094 1000000000095 1000000000097
1000000000099 1000000000101 1000000000102 1000000000103
1000000000105 1000000000106 1000000000109 1000000000111
1000000000113 1000000000114 1000000000115 1000000000117
1000000000118 1000000000119 1000000000121 1000000000122
1000000000123 1000000000126 1000000000127 1000000000129
1000000000130 1000000000133 1000000000135 1000000000137
1000000000138 1000000000139 1000000000141 1000000000142
1000000000145
square free count
[1 to limit]
10 7
100 61
1000 608
10000 6083
100000 60794
1000000 607926
10000000 6079291
100000000 60792694
1000000000 607927124
10000000000 6079270942
real 0m13,908s</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
| |||