CCM0128 - Computação II (2025i)

Dizemos que um número natural positivo é simples se ele não tem divisores primos maiores que \(7\). Assim, um número simples é da forma $2^a3^b5^c7^d$, onde $a$, $b$, $c$ e $d$ são números naturais. Os primeiros $20$ números simples são

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27.

Neste exercício, você deve escrever uma função que devolve o $N$-ésimo número simples para valores moderadamente grandes de $N$ dados pelo usuário. Por exemplo, para $N=20$, sua função deve devolver $27$.

BigIntegers.  Como queremos trabalhar com números simples grandes (que não cabem em um long), você deverá usar a classe BigInteger do Java. Este é o documento oficial com a descrição dessa classe.

Para uma introdução simples a essa classe, veja, por exemplo, esta página. (O programa Example.java desta página, levemente modificado, segue abaixo.)

Sua tarefa.  Sua tarefa é escrever uma classe chamada Simple.java, que contém uma função de assinatura

public static BigInteger nthSimple(int N)

que, ao receber $N\geq1$, devolve o $N$-ésimo número simples. Sua função será testada com a classe SimpleClient.java dada abaixo e de algumas outras formas.

Exemplos de execução.  Seguem alguns exemplos de execução:

$ java-introcs SimpleClient 10000
Elapsed time: 0.0
63221760000
$ java-introcs SimpleClient 10000000
Elapsed time: 5.8
1037754506929393275846369194817675812165052808572460991244140544000
$ java-introcs SimpleClient 20000000
Elapsed time: 13.4
5315584217176796584956949434687386531552635487727820873260498046875000000000000
$ java-introcs SimpleClient 40000000
Elapsed time: 29.4
6916111798394576685578982249831634905831344091020982877920731406301259994506835937500000000000
$ java-introcs SimpleClient 100000000
Elapsed time: 92.7
19740298131032654812472710905349395789786394159462319333658845201548773240496359449025476351380348205566406250000000000
$

Desempenho.  O desempenho de sua função nthSimple() deve ser grosso modo comparável ao desempenho que você vê nos exemplos acima.

Entrega.  Entregue apenas sua classe Simple.java.