57 lines
1.2 KiB
D
57 lines
1.2 KiB
D
import std.math;
|
|
import std.stdio;
|
|
|
|
immutable MU_MAX = 1_000_000;
|
|
|
|
int mobiusFunction(int n) {
|
|
static initialized = false;
|
|
static int[MU_MAX + 1] MU;
|
|
|
|
if (initialized) {
|
|
return MU[n];
|
|
}
|
|
|
|
// populate array
|
|
MU[] = 1;
|
|
int root = cast(int) sqrt(cast(real) MU_MAX);
|
|
|
|
for (int i = 2; i <= root; i++) {
|
|
if (MU[i] == 1) {
|
|
// for each factor found, swap + and -
|
|
for (int j = i; j <= MU_MAX; j += i) {
|
|
MU[j] *= -i;
|
|
}
|
|
// square factor = 0
|
|
for (int j = i * i; j <= MU_MAX; j += i * i) {
|
|
MU[j] = 0;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int i = 2; i <= MU_MAX; i++) {
|
|
if (MU[i] == i) {
|
|
MU[i] = 1;
|
|
} else if (MU[i] == -i) {
|
|
MU[i] = -1;
|
|
} else if (MU[i] < 0) {
|
|
MU[i] = 1;
|
|
} else if (MU[i] > 0) {
|
|
MU[i] = -1;
|
|
}
|
|
}
|
|
|
|
initialized = true;
|
|
return MU[n];
|
|
}
|
|
|
|
void main() {
|
|
writeln("First 199 terms of the möbius function are as follows:");
|
|
write(" ");
|
|
for (int n = 1; n < 200; n++) {
|
|
writef("%2d ", mobiusFunction(n));
|
|
if ((n + 1) % 20 == 0) {
|
|
writeln;
|
|
}
|
|
}
|
|
}
|