Sequence: nth number with exactly n divisors: Difference between revisions
Sequence: nth number with exactly n divisors (view source)
Revision as of 17:27, 13 June 2021
, 2 years ago→{{header|C++}}
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 14:
:*[[Sequence: smallest number greater than previous term with exactly n divisors]]
:*[[Sequence: smallest number with exactly n divisors]]
=={{header|C}}==
{{trans|C++}}
<lang c>#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#define LIMIT 15
int smallPrimes[LIMIT];
static void sieve() {
int i = 2, j;
int p = 5;
smallPrimes[0] = 2;
smallPrimes[1] = 3;
while (i < LIMIT) {
for (j = 0; j < i; j++) {
if (smallPrimes[j] * smallPrimes[j] <= p) {
if (p % smallPrimes[j] == 0) {
p += 2;
break;
}
} else {
smallPrimes[i++] = p;
p += 2;
break;
}
}
}
}
static bool is_prime(uint64_t n) {
uint64_t i;
for (i = 0; i < LIMIT; i++) {
if (n % smallPrimes[i] == 0) {
return n == smallPrimes[i];
}
}
i = smallPrimes[LIMIT - 1] + 2;
for (; i * i <= n; i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
static uint64_t divisor_count(uint64_t n) {
uint64_t count = 1;
uint64_t d;
while (n % 2 == 0) {
n /= 2;
count++;
}
for (d = 3; d * d <= n; d += 2) {
uint64_t q = n / d;
uint64_t r = n % d;
uint64_t dc = 0;
while (r == 0) {
dc += count;
n = q;
q = n / d;
r = n % d;
}
count += dc;
}
if (n != 1) {
return count *= 2;
}
return count;
}
static uint64_t OEISA073916(size_t n) {
uint64_t count = 0;
uint64_t result = 0;
size_t i;
if (is_prime(n)) {
return (uint64_t)pow(smallPrimes[n - 1], n - 1);
}
for (i = 1; count < n; i++) {
if (n % 2 == 1) {
// The solution for an odd (non-prime) term is always a square number
uint64_t root = (uint64_t)sqrt(i);
if (root * root != i) {
continue;
}
}
if (divisor_count(i) == n) {
count++;
result = i;
}
}
return result;
}
int main() {
size_t n;
sieve();
for (n = 1; n <= LIMIT; n++) {
if (n == 13) {
printf("A073916(%lu) = One more bit needed to represent result.\n", n);
} else {
printf("A073916(%lu) = %llu\n", n, OEISA073916(n));
}
}
return 0;
}</lang>
{{out}}
<pre>A073916(1) = 1
A073916(2) = 3
A073916(3) = 25
A073916(4) = 14
A073916(5) = 14641
A073916(6) = 44
A073916(7) = 24137569
A073916(8) = 70
A073916(9) = 1089
A073916(10) = 405
A073916(11) = 819628286980801
A073916(12) = 160
A073916(13) = One more bit needed to represent result.
A073916(14) = 2752
A073916(15) = 9801</pre>
=={{header|C++}}==
| |||