Pan base non-primes: Difference between revisions
Content added Content deleted
(Added C++ solution) |
(Added C solution) |
||
Line 167: | Line 167: | ||
Number odd = 161 or 16.894019% |
Number odd = 161 or 16.894019% |
||
Number even = 792 or 83.105981% |
Number even = 792 or 83.105981% |
||
</pre> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="c">#include <stdbool.h> |
|||
#include <stdint.h> |
|||
#include <stdio.h> |
|||
bool is_prime(uint64_t n) { |
|||
if (n < 2) |
|||
return false; |
|||
if (n % 2 == 0) |
|||
return n == 2; |
|||
if (n % 3 == 0) |
|||
return n == 3; |
|||
if (n % 5 == 0) |
|||
return n == 5; |
|||
static const uint64_t wheel[] = {4, 2, 4, 2, 4, 6, 2, 6}; |
|||
for (uint64_t p = 7;;) { |
|||
for (int i = 0; i < 8; ++i) { |
|||
if (p * p > n) |
|||
return true; |
|||
if (n % p == 0) |
|||
return false; |
|||
p += wheel[i]; |
|||
} |
|||
} |
|||
} |
|||
// Compute the digits of n in base 10, least significant digit first. |
|||
int digits(uint64_t n, uint8_t* d, int size) { |
|||
int count = 0; |
|||
for (; n > 0 && size > 0; n /= 10, --size, ++count) |
|||
*d++ = n % 10; |
|||
return count; |
|||
} |
|||
// Convert digits in the given base to a number (least significant digit first). |
|||
uint64_t from_digits(uint8_t* a, int count, uint64_t base) { |
|||
uint64_t n = 0; |
|||
while (count-- > 0) |
|||
n = n * base + a[count]; |
|||
return n; |
|||
} |
|||
#define MAX_DIGITS 20 |
|||
bool is_pan_base_non_prime(uint64_t n) { |
|||
if (n < 10) |
|||
return !is_prime(n); |
|||
if (n > 10 && n % 10 == 0) |
|||
return true; |
|||
uint8_t d[MAX_DIGITS]; |
|||
int count = digits(n, d, MAX_DIGITS); |
|||
uint8_t max_digit = 0; |
|||
for (int i = 0; i < count; ++i) { |
|||
if (max_digit < d[i]) |
|||
max_digit = d[i]; |
|||
} |
|||
for (uint64_t base = max_digit + 1; base <= n; ++base) { |
|||
if (is_prime(from_digits(d, count, base))) |
|||
return false; |
|||
} |
|||
return true; |
|||
} |
|||
int main() { |
|||
printf("First 50 prime pan-base composites:\n"); |
|||
int count = 0; |
|||
for (uint64_t n = 2; count < 50; ++n) { |
|||
if (is_pan_base_non_prime(n)) { |
|||
++count; |
|||
printf("%3llu%c", n, count % 10 == 0 ? '\n' : ' '); |
|||
} |
|||
} |
|||
printf("\nFirst 20 odd prime pan-base composites:\n"); |
|||
count = 0; |
|||
for (uint64_t n = 3; count < 20; n += 2) { |
|||
if (is_pan_base_non_prime(n)) { |
|||
++count; |
|||
printf("%3llu%c", n, count % 10 == 0 ? '\n' : ' '); |
|||
} |
|||
} |
|||
const uint64_t limit = 10000; |
|||
int odd = 0; |
|||
count = 0; |
|||
for (uint64_t n = 2; n <= limit; ++n) { |
|||
if (is_pan_base_non_prime(n)) { |
|||
++count; |
|||
if (n % 2 == 1) |
|||
++odd; |
|||
} |
|||
} |
|||
printf("\nCount of pan-base composites up to and including %llu: %d\n", |
|||
limit, count); |
|||
double percent = 100.0 * odd / count; |
|||
printf("Percent odd up to and including %llu: %f\n", limit, percent); |
|||
printf("Percent even up to and including %llu: %f\n", limit, |
|||
100.0 - percent); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 50 prime pan-base composites: |
|||
4 6 8 9 20 22 24 26 28 30 |
|||
33 36 39 40 42 44 46 48 50 55 |
|||
60 62 63 64 66 68 69 70 77 80 |
|||
82 84 86 88 90 93 96 99 100 110 |
|||
112 114 116 118 120 121 130 132 134 136 |
|||
First 20 odd prime pan-base composites: |
|||
9 33 39 55 63 69 77 93 99 121 |
|||
143 165 169 187 231 253 273 275 297 299 |
|||
Count of pan-base composites up to and including 10000: 3849 |
|||
Percent odd up to and including 10000: 18.030657 |
|||
Percent even up to and including 10000: 81.969343 |
|||
</pre> |
</pre> |
||