Square-free integers: Difference between revisions
Content added Content deleted
m (C++ solution made faster) |
|||
Line 478: | Line 478: | ||
Number of square-free numbers between 1 and 1000000: 607926 |
Number of square-free numbers between 1 and 1000000: 607926 |
||
</pre> |
</pre> |
||
=={{header|D}}== |
|||
{{trans|Java}} |
|||
<lang d>import std.array; |
|||
import std.math; |
|||
import std.stdio; |
|||
long[] sieve(long limit) { |
|||
long[] primes = [2]; |
|||
bool[] c = uninitializedArray!(bool[])(cast(size_t)(limit + 1)); |
|||
long p = 3; |
|||
while (true) { |
|||
long p2 = p * p; |
|||
if (p2 > limit) { |
|||
break; |
|||
} |
|||
for (long i = p2; i <= limit; i += 2 * p) { |
|||
c[cast(size_t)i] = true; |
|||
} |
|||
while (true) { |
|||
p += 2; |
|||
if (!c[cast(size_t)p]) { |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
for (long i = 3; i <= limit; i += 2) { |
|||
if (!c[cast(size_t)i]) { |
|||
primes ~= i; |
|||
} |
|||
} |
|||
return primes; |
|||
} |
|||
long[] squareFree(long from, long to) { |
|||
long limit = cast(long)sqrt(cast(real)to); |
|||
auto primes = sieve(limit); |
|||
long[] results; |
|||
outer: |
|||
for (long i = from; i <= to; i++) { |
|||
foreach (p; primes) { |
|||
long p2 = p * p; |
|||
if (p2 > i) { |
|||
break; |
|||
} |
|||
if (i % p2 == 0) { |
|||
continue outer; |
|||
} |
|||
} |
|||
results ~= i; |
|||
} |
|||
return results; |
|||
} |
|||
enum TRILLION = 1_000_000_000_000L; |
|||
void main() { |
|||
writeln("Square-free integers from 1 to 145:"); |
|||
auto sf = squareFree(1, 145); |
|||
foreach (i,v; sf) { |
|||
if (i > 0 && i % 20 == 0) { |
|||
writeln; |
|||
} |
|||
writef("%4d", v); |
|||
} |
|||
writefln("\n\nSquare-free integers from %d to %d:", TRILLION, TRILLION + 145); |
|||
sf = squareFree(TRILLION, TRILLION + 145); |
|||
foreach (i,v; sf) { |
|||
if (i > 0 && i % 5 == 0) { |
|||
writeln; |
|||
} |
|||
writef("%14d", v); |
|||
} |
|||
writeln("\n\nNumber of square-free integers:"); |
|||
foreach (to; [100, 1_000, 10_000, 100_000, 1_000_000]) { |
|||
writefln(" from 1 to %d = %d", to, squareFree(1, to).length); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>Square-free integers 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 integers 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 |
|||
Number of square-free integers: |
|||
from 1 to 100 = 61 |
|||
from 1 to 1000 = 608 |
|||
from 1 to 10000 = 6083 |
|||
from 1 to 100000 = 60794 |
|||
from 1 to 1000000 = 607926</pre> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |