Sequence: nth number with exactly n divisors: Difference between revisions

Content added Content deleted
(→‎{{header|Factor}}: fix prime function, update output)
Line 405: Line 405:


=={{header|Java}}==
=={{header|Java}}==

{{trans|Go}}
Replace translation with Java native implementation.
<lang java>import java.util.ArrayList;

<lang java>
import java.math.BigInteger;
import java.math.BigInteger;
import static java.lang.Math.sqrt;
import java.util.ArrayList;
import java.util.List;


public class OEIS_A073916 {
public class SequenceNthNumberWithExactlyNDivisors {


static boolean is_prime(int n) {
public static void main(String[] args) {
int max = 45;
return BigInteger.valueOf(n).isProbablePrime(10);
smallPrimes(max);
for ( int n = 1; n <= max ; n++ ) {
System.out.printf("A073916(%d) = %s%n", n, OEISA073916(n));
}
}
}

static ArrayList<Integer> generate_small_primes(int n) {
private static List<Integer> smallPrimes = new ArrayList<>();
ArrayList<Integer> primes = new ArrayList<Integer>();
private static void smallPrimes(int numPrimes) {
primes.add(2);
for (int i = 3; primes.size() < n; i += 2) {
smallPrimes.add(2);
for ( int n = 3, count = 0 ; count < numPrimes ; n += 2 ) {
if (is_prime(i)) primes.add(i);
if ( isPrime(n) ) {
smallPrimes.add(n);
count++;
}
}
}
}
return primes;
private static final boolean isPrime(long test) {
if ( test == 2 ) {
return true;
}
if ( test % 2 == 0 ) {
return false;
}
for ( long d = 3 ; d*d <= test ; d += 2 ) {
if ( test % d == 0 ) {
return false;
}
}
return true;
}
}


static int count_divisors(int n) {
private static int getDivisorCount(long n) {
int count = 1;
int count = 1;
while (n % 2 == 0) {
while ( n % 2 == 0 ) {
n >>= 1;
n /= 2;
++count;
count += 1;
}
}
for (int d = 3; d * d <= n; d += 2) {
for ( long d = 3 ; d*d <= n ; d += 2 ) {
int q = n / d;
long q = n / d;
int r = n % d;
long r = n % d;
if (r == 0) {
int dc = 0;
int dc = 0;
while ( r == 0 ) {
while (r == 0) {
dc += count;
dc += count;
n = q;
n = q;
q = n / d;
q = n / d;
r = n % d;
r = n % d;
}
count += dc;
}
}
count += dc;
}
if ( n != 1 ) {
count *= 2;
}
}
if (n != 1) count *= 2;
return count;
return count;
}
}

public static void main(String[] args) {
private static BigInteger OEISA073916(int n) {
final int max = 33;
if ( isPrime(n) ) {
return BigInteger.valueOf(smallPrimes.get(n-1)).pow(n - 1);
ArrayList<Integer> primes = generate_small_primes(max);
}
System.out.printf("The first %d terms of the sequence are:\n", max);
for (int i = 1; i <= max; ++i) {
int count = 0;
if (is_prime(i)) {
int result = 0;
BigInteger z = BigInteger.valueOf(primes.get(i - 1));
for ( int i = 1 ; count < n ; i++ ) {
z = z.pow(i - 1);
if ( n % 2 == 1 ) {
// The solution for an odd (non-prime) term is always a square number
System.out.printf("%2d : %d\n", i, z);
} else {
int sqrt = (int) Math.sqrt(i);
for (int j = 1, count = 0; ; ++j) {
if ( sqrt*sqrt != i ) {
if (i % 2 == 1) {
continue;
int sq = (int)sqrt(j);
if (sq * sq != j) continue;
}
if (count_divisors(j) == i) {
if (++count == i) {
System.out.printf("%2d : %d\n", i, j);
break;
}
}
}
}
}
if ( getDivisorCount(i) == n ) {
count++;
result = i;
}
}
}
}
return BigInteger.valueOf(result);
}
}

}</lang>
}
</lang>


{{out}}
{{out}}
<pre>
<pre>
A073916(1) = 1
The first 33 terms of the sequence are:
A073916(2) = 3
1 : 1
A073916(3) = 25
2 : 3
A073916(4) = 14
3 : 25
A073916(5) = 14641
4 : 14
A073916(6) = 44
5 : 14641
A073916(7) = 24137569
6 : 44
A073916(8) = 70
7 : 24137569
A073916(9) = 1089
8 : 70
A073916(10) = 405
9 : 1089
A073916(11) = 819628286980801
10 : 405
A073916(12) = 160
11 : 819628286980801
A073916(13) = 22563490300366186081
12 : 160
A073916(14) = 2752
13 : 22563490300366186081
A073916(15) = 9801
14 : 2752
A073916(16) = 462
15 : 9801
A073916(17) = 21559177407076402401757871041
16 : 462
A073916(18) = 1044
17 : 21559177407076402401757871041
A073916(19) = 740195513856780056217081017732809
18 : 1044
A073916(20) = 1520
19 : 740195513856780056217081017732809
A073916(21) = 141376
20 : 1520
A073916(22) = 84992
21 : 141376
A073916(23) = 1658509762573818415340429240403156732495289
22 : 84992
A073916(24) = 1170
23 : 1658509762573818415340429240403156732495289
A073916(25) = 52200625
24 : 1170
A073916(26) = 421888
25 : 52200625
A073916(27) = 52900
26 : 421888
A073916(28) = 9152
27 : 52900
A073916(29) = 1116713952456127112240969687448211536647543601817400964721
28 : 9152
A073916(30) = 6768
29 : 1116713952456127112240969687448211536647543601817400964721
A073916(31) = 1300503809464370725741704158412711229899345159119325157292552449
30 : 6768
A073916(32) = 3990
31 : 1300503809464370725741704158412711229899345159119325157292552449
A073916(33) = 12166144
32 : 3990
A073916(34) = 9764864
33 : 12166144
A073916(35) = 446265625
A073916(36) = 5472
A073916(37) = 11282036144040442334289838466416927162302790252609308623697164994458730076798801
A073916(38) = 43778048
A073916(39) = 90935296
A073916(40) = 10416
A073916(41) = 1300532588674810624476094551095787816112173600565095470117230812218524514342511947837104801
A073916(42) = 46400
A073916(43) = 635918448514386699807643535977466343285944704172890141356181792680152445568879925105775366910081
A073916(44) = 240640
A073916(45) = 327184
</pre>
</pre>



=={{header|Julia}}==
=={{header|Julia}}==
Retrieved from "https://rosettacode.org/wiki/Sequence:_nth_number_with_exactly_n_divisors"