Pairs with common factors: Difference between revisions
Added C
(Added Algol 68) |
(Added C) |
||
Line 119:
a(100000): 1960299247
a(1000000): 196035947609
</pre>
=={{header|C}}==
{{trans|Wren}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <locale.h>
#define MAX 1000000
bool isPrime(int n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
int d = 5;
while (d*d <= n) {
if (n%d == 0) return false;
d += 2;
if (n%d == 0) return false;
d += 4;
}
return true;
}
uint64_t totient(uint64_t n) {
uint64_t tot = n, i = 2;
while (i*i <= n) {
if (!(n%i)) {
do {n /= i;} while (!(n%i));
tot -= tot/i;
}
if (i == 2) i = 1;
i += 2;
}
if (n > 1) tot -= tot/n;
return tot;
}
const char *ord(int c) {
int m = c % 100;
if (m >= 4 && m <= 20) return "th";
m %= 10;
return (m == 1) ? "st" :
(m == 2) ? "nd" :
(m == 3) ? "rd" : "th";
}
int main() {
uint64_t n, sumPhi = 0, *a = (uint64_t *)calloc(MAX, sizeof(uint64_t));
int i, limit;
for (n = 1; n <= MAX; ++n) {
sumPhi += totient(n);
if (isPrime(n)) {
a[n-1] = a[n-2];
} else {
a[n-1] = n*(n-1)/2 + 1 - sumPhi;
}
}
setlocale(LC_NUMERIC, "");
printf("Number of pairs with common factors - first one hundred terms:\n");
for (i = 0; i < 100; ++i) {
printf("%'5lu ", a[i]);
if (!((i+1)%10)) printf("\n");
}
printf("\n");
for (limit = 1; limit <= MAX; limit *= 10) {
printf("The %'d%s term: %'lu\n", limit, ord(limit), a[limit-1]);
}
free(a);
return 0;
}</syntaxhighlight>
{{out}}
<pre>
Number of pairs with common factors - first one hundred terms:
0 0 0 1 1 4 4 7 9 14
14 21 21 28 34 41 41 52 52 63
71 82 82 97 101 114 122 137 137 158
158 173 185 202 212 235 235 254 268 291
291 320 320 343 363 386 386 417 423 452
470 497 497 532 546 577 597 626 626 669
669 700 726 757 773 818 818 853 877 922
922 969 969 1,006 1,040 1,079 1,095 1,148 1,148 1,195
1,221 1,262 1,262 1,321 1,341 1,384 1,414 1,461 1,461 1,526
1,544 1,591 1,623 1,670 1,692 1,755 1,755 1,810 1,848 1,907
The 1st term: 0
The 10th term: 14
The 100th term: 1,907
The 1,000th term: 195,309
The 10,000th term: 19,597,515
The 100,000th term: 1,960,299,247
The 1,000,000th term: 196,035,947,609
</pre>
| |||