_________________________________________________________________________
What is the sum of all emirps up to X?
Sample input
100 200
Sample output
418 1489
TEST
449923069
NOTE: According to wikipedia, an emirp (prime spelled backwards) is a prime number that results in a different prime when its digits are reversed. This definition excludes the related palindromic primes. Emirps are also called reversible primes. The sequence of emirps begins 13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157… All non-palindromic permutable primes are emirps.
_________________________________________________________________________
UserInterface Class:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Clase encargada de mantener el bucle de ejecución del programa hasta el fin de linea.
* @author Javier de Pedro López
*/
public class UserInterface {
/**
* Permite mantener el bucle de lecutra.
*/
public void run() throws IOException{
String line;
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
//Bucle que realiza las lecturas hasta que lo recibido sea EOF (null)
do{
line = reader.readLine();
if (line != null && !line.trim().equals("")){
Long number = new Long(line.trim());
SumEmirp sum = new SumEmirp(number);
System.out.println(sum.getSum());
}
} while(line != null);
}
}
SumEmirp Class:
/**
* Permite obtener la suma de los emirps.
* @author Javier de Pedro López
*/
public class SumEmirp {
private long _sum;
/**
* Instancia una nueva suma de Emirps.
* @param number hasta el que se quiere realizar la suma.
*/
public SumEmirp (long number){
_sum = 0;
for (long i = 2; i <= number; i++ ){
if (i != reverse(new Long(i).toString()) && isPrime(i) && isPrime(reverse(new Long(i).toString()))){
_sum += i;
}
}
}
/**
* Permite obtener la suma de emirps.
* @return la suma de emirps.
*/
public long getSum(){
return _sum;
}
/**
* Permite conocer si un numero es primo o no.
* @param number numero del que queremos conocer la primalidad.
* @return true si es primo y false si no lo es.
*/
private boolean isPrime (long number){
boolean isPrime = true;
for (long i = 3; i <= Math.sqrt(number); i += 2)
if (number % i == 0) {
isPrime = false;
break;
}
if (( number%2 !=0 && isPrime && number > 2) || number == 2) {
return true;
} else {
return false;
}
}
/**
* Le da la vuelta a un numero que se pasa como String.
* @param number numero al que queremos darle la vuelta.
* @return el numero en forma de entero con el valor dado la vuelta.
*/
private int reverse(String number){
String numReverse = "";
for (int i = number.length()-1; i >= 0; i--){
numReverse += number.charAt(i);
}
return Integer.valueOf(numReverse);
}
}
Eratostenes Class:
import java.math.BigInteger;
import java.util.ArrayList;
/**
* Permite ejecutar el algoritmo de la criba de eratostenes.
* @author Javier de Pedro López
*/
public class Eratostenes {
//ATRIBUTOS//
private ArrayList<Long> _eratostenes;
private ArrayList<Long> _emirp;
private long _maxnum;
//CONSTRUCTORES//
/**
* Instancia un nuevo elemento para realizar la criba.
*/
public Eratostenes(long num){
_maxnum = num;
_eratostenes = new ArrayList<Long>();
_emirp = new ArrayList<Long>();
//Calculamos la primera lista de primos respecto al maximo valor dado
for (long i = 2; i <= _maxnum; i++){
_eratostenes.add(i);
}
deleteNumbers(_maxnum);
//Calculamos la lista del primos del mayor indice de los inversos primos de la primera lista
long maxEmirp = getMaxEratostenesEmirp();
if (maxEmirp > _maxnum){
for (long i = _maxnum + 1; i <= maxEmirp; i++){
_eratostenes.add(i);
}
deleteNumbers(maxEmirp);
}
//Agregamos los elementos que sean emirps a la lista de emirps
for (int i = 0; i < _eratostenes.size() && _eratostenes.get(i) <= _maxnum; i++){
if (reverse(_eratostenes.get(i).toString()) != _eratostenes.get(i) && _eratostenes.contains(new Long(reverse(_eratostenes.get(i).toString())))){
System.out.println(_eratostenes.get(i));
_emirp.add(_eratostenes.get(i));
}
}
}
//METODOS//
/**
* Elimina todos los numeros que no son primos.
*/
private void deleteNumbers(long max){
for (long i = 2; i <= Math.sqrt(max); i++){
if (_eratostenes.contains(i)){
long j = 2;
while(i * j <= max){
if (_eratostenes.contains(i*j)){
_eratostenes.remove(new Long(i*j));
}
j++;
}
}
}
}
/**
* Permite obtener la suma de todos los emirps
* @return
*/
public BigInteger getSumEratostenesEmirp(){
BigInteger sum = new BigInteger ("0");
for (int i = 0; i < _emirp.size(); i++){
sum = sum.add(new BigInteger(_emirp.get(i).toString()));
}
return sum;
}
/**
* Permite obtener el mayor de todos los numeros dados la vuelta siendo primos.
* @return el mayor de los numeros primos dado la vuelta.
*/
public long getMaxEratostenesEmirp(){
long max = 0;
for (int i = 0; i < _eratostenes.size(); i++){
long reverse = reverse(_eratostenes.get(i).toString());
if (reverse > max){
max = reverse;
}
}
return max;
}
/**
* Le da la vuelta a un numero que se pasa como String.
* @param number numero al que queremos darle la vuelta.
* @return el numero en forma de entero con el valor dado la vuelta.
*/
private int reverse(String number){
String numReverse = "";
for (int i = number.length()-1; i >= 0; i--){
numReverse += number.charAt(i);
}
return Integer.valueOf(numReverse);
}
}