56 lines
1.1 KiB
C
56 lines
1.1 KiB
C
#include <math.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
int main() {
|
|
const int MU_MAX = 1000000;
|
|
int i, j;
|
|
int *mu;
|
|
int sqroot;
|
|
|
|
sqroot = (int)sqrt(MU_MAX);
|
|
|
|
mu = malloc((MU_MAX + 1) * sizeof(int));
|
|
|
|
for (i = 0; i < MU_MAX;i++) {
|
|
mu[i] = 1;
|
|
}
|
|
|
|
for (i = 2; i <= sqroot; i++) {
|
|
if (mu[i] == 1) {
|
|
// for each factor found, swap + and -
|
|
for (j = i; j <= MU_MAX; j += i) {
|
|
mu[j] *= -i;
|
|
}
|
|
// square factor = 0
|
|
for (j = i * i; j <= MU_MAX; j += i * i) {
|
|
mu[j] = 0;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (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;
|
|
}
|
|
}
|
|
|
|
printf("First 199 terms of the möbius function are as follows:\n ");
|
|
for (i = 1; i < 200; i++) {
|
|
printf("%2d ", mu[i]);
|
|
if ((i + 1) % 20 == 0) {
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
free(mu);
|
|
return 0;
|
|
}
|