70 lines
2 KiB
C
70 lines
2 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
#include <locale.h>
|
|
|
|
bool *primeSieve(int limit) {
|
|
int i, p;
|
|
limit++;
|
|
// True denotes composite, false denotes prime.
|
|
bool *c = calloc(limit, sizeof(bool)); // all false by default
|
|
c[0] = true;
|
|
c[1] = true;
|
|
for (i = 4; i < limit; i += 2) c[i] = true;
|
|
p = 3; // Start from 3.
|
|
while (true) {
|
|
int p2 = p * p;
|
|
if (p2 >= limit) break;
|
|
for (i = p2; i < limit; i += 2 * p) c[i] = true;
|
|
while (true) {
|
|
p += 2;
|
|
if (!c[p]) break;
|
|
}
|
|
}
|
|
return c;
|
|
}
|
|
|
|
int main() {
|
|
const int limit = 1000000;
|
|
int i, j, n, uc = 2, p = 10, m = 63, ul = 151000;
|
|
bool *c = primeSieve(limit);
|
|
n = m * limit + 1;
|
|
int *sumDivs = (int *)calloc(n, sizeof(int));
|
|
for (i = 1; i < n; ++i) {
|
|
for (j = i; j < n; j += i) sumDivs[j] += i;
|
|
}
|
|
bool *s = (bool *)calloc(n, sizeof(bool)); // all false
|
|
for (i = 1; i < n; ++i) {
|
|
int sum = sumDivs[i] - i; // proper divs sum
|
|
if (sum <= n) s[sum] = true;
|
|
}
|
|
free(sumDivs);
|
|
int *untouchable = (int *)malloc(ul * sizeof(int));
|
|
untouchable[0] = 2;
|
|
untouchable[1] = 5;
|
|
for (n = 6; n <= limit; n += 2) {
|
|
if (!s[n] && c[n-1] && c[n-3]) untouchable[uc++] = n;
|
|
}
|
|
setlocale(LC_NUMERIC, "");
|
|
printf("List of untouchable numbers <= 2,000:\n");
|
|
for (i = 0; i < uc; ++i) {
|
|
j = untouchable[i];
|
|
if (j > 2000) break;
|
|
printf("%'6d ", j);
|
|
if (!((i+1) % 10)) printf("\n");
|
|
}
|
|
printf("\n\n%'7d untouchable numbers were found <= 2,000\n", i);
|
|
for (i = 0; i < uc; ++i) {
|
|
j = untouchable[i];
|
|
if (j > p) {
|
|
printf("%'7d untouchable numbers were found <= %'9d\n", i, p);
|
|
p *= 10;
|
|
if (p == limit) break;
|
|
}
|
|
}
|
|
printf("%'7d untouchable numbers were found <= %'d\n", uc, limit);
|
|
free(c);
|
|
free(s);
|
|
free(untouchable);
|
|
return 0;
|
|
}
|