Primos Apagáveis
Um número primo apagável é um número primo ao qual se podem remover
todos os dı́gitos, um, e apenas um, de cada vez, obtendo números primos a
cada passo.
Por exemplo, o número 4125673 é um número primo apagável, atendendo a que os números da sequência:
4125673
415673
45673
4567
467
67
7
são todos números primos (apagáveis).
Note que, para um número ser número primo apagável, basta que exista
uma destas sequências de números primos.
Note ainda que, o número 10859 não é um número primo apagável, visto
não existir nenhuma sequência de acordo com a definição. Em particular a
sequência:
10859
859
59
5
é inválida. Isto porque ao remover o 1 de 10859 são removidos, na realidade,
dois digitos (o 1 e o 0), o que contraria a definição de número primo apagável,
onde se indica, claramente, que apenas um digito pode ser removido a cada
passo.
Note finalmente que, pela definição, o número 1 não é um número primo.
Pretende-se que implemente um programa que calcule a soma de todos
os números primos apagáveis num dado intervalo.
O trabalho será avaliado usando o sistema Mooshak, através de um conjunto de testes de dificuldade progressiva. Como habitualmente, deverá
submeter o seu trabalho num arquivo zip em que a classe contendo a função
main deverá chamar-se Main e estar contida na package poo. O seu programa
terá um máximo de 5 segundos para completar cada um dos testes. A nota
a atribuir será proporcional ao número de testes passados dentro do limite
temporal definido, podendo ir até aos 3 pontos. Os testes disponı́veis no
Moodle são de dificuldade igual aos usados no Mooshak. Dada a natureza
do presente trabalho não haverá qualquer penalização devido ao número de
submissões ao Mooshak.
1
Input
O input consiste numa sequência de pares de números inteiros positivos, i e
j, um par por linha. Todos os inteiros serão menores que 10,000,000. Pode
ainda assumir que i é menor ou igual a j. Deverá processar todos os pares
de inteiros, calculando para cada par a soma de todos os números primos
apagáveis entre i e j, inclusivé. O input termina com uma linha contendo
apenas -1.
Output
Para cada par de números inteiros, definindo um intervalo, deverá imprimir
a soma de todos os números primos apagáveis no intervalo, ou nenhum
caso não exista qualquer número primo apagável no intervalo.
Exemplo de Input
1 100
1000 1010
10859 10859
4125673 4125673
1 9999999
-1
Exemplo de Output
839
nenhum
nenhum
4125673
985882477926
Sugestão
Não deixe de investigar formas mais eficientes de resolver o problema, procurando, por exemplo, formas expeditas de determinar se um número é ou
não primo, ou é ou não primo apagável, ou tabelando valores de forma a
não ter que os recalcular para cada intervalo.
2