Colorful numbers: Difference between revisions
Added C solution
(Add Factor) |
(Added C solution) |
||
Line 33:
''Colorful numbers have no real number theory application. They are more a recreational math puzzle than a useful tool.''
=={{header|C}}==
The <code>count_colorful</code> function is based on [[#Phix|Phix]].
<lang c>#include <locale.h>
#include <stdbool.h>
#include <stdio.h>
#include <time.h>
bool colorful(int n) {
// A colorful number cannot be greater than 98765432.
if (n < 0 || n > 98765432)
return false;
int digit_count[10] = {};
int digits[8] = {};
int num_digits = 0;
for (int m = n; m > 0; m /= 10) {
int d = m % 10;
if (n > 9 && (d == 0 || d == 1))
return false;
if (++digit_count[d] > 1)
return false;
digits[num_digits++] = d;
}
// Maximum number of products is (8 x 9) / 2.
int products[36] = {};
for (int i = 0, product_count = 0; i < num_digits; ++i) {
for (int j = i, p = 1; j < num_digits; ++j) {
p *= digits[j];
for (int k = 0; k < product_count; ++k) {
if (products[k] == p)
return false;
}
products[product_count++] = p;
}
}
return true;
}
static int count[8];
static bool used[10];
static int largest = 0;
void count_colorful(int taken, int n, int digits) {
if (taken == 0) {
for (int d = 0; d < 10; ++d) {
used[d] = true;
count_colorful(d < 2 ? 9 : 1, d, 1);
used[d] = false;
}
} else {
if (colorful(n)) {
++count[digits - 1];
if (n > largest)
largest = n;
}
if (taken < 9) {
for (int d = 2; d < 10; ++d) {
if (!used[d]) {
used[d] = true;
count_colorful(taken + 1, n * 10 + d, digits + 1);
used[d] = false;
}
}
}
}
}
int main() {
setlocale(LC_ALL, "");
clock_t start = clock();
printf("Colorful numbers less than 100:\n");
for (int n = 0, count = 0; n < 100; ++n) {
if (colorful(n))
printf("%2d%c", n, ++count % 10 == 0 ? '\n' : ' ');
}
count_colorful(0, 0, 0);
printf("\n\nLargest colorful number: %'d\n", largest);
printf("\nCount of colorful numbers by number of digits:\n");
int total = 0;
for (int d = 0; d < 8; ++d) {
printf("%d %'d\n", d + 1, count[d]);
total += count[d];
}
printf("\nTotal: %'d\n", total);
clock_t end = clock();
printf("\nElapsed time: %f seconds\n",
(end - start + 0.0) / CLOCKS_PER_SEC);
return 0;
}</lang>
{{out}}
<pre>
Colorful numbers less than 100:
0 1 2 3 4 5 6 7 8 9
23 24 25 26 27 28 29 32 34 35
36 37 38 39 42 43 45 46 47 48
49 52 53 54 56 57 58 59 62 63
64 65 67 68 69 72 73 74 75 76
78 79 82 83 84 85 86 87 89 92
93 94 95 96 97 98
Largest colorful number: 98,746,253
Count of colorful numbers by number of digits:
1 10
2 56
3 328
4 1,540
5 5,514
6 13,956
7 21,596
8 14,256
Total: 57,256
Elapsed time: 0.024598 seconds
</pre>
=={{header|Factor}}==
| |||