Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
11105 – Semi-prime H-numbers

El problema es de teoría de números.
Lo que nos dicen es que los números H son de la forma 4n + 1.
Los H primos son los que pertenecen a este conjunto y ademas solo se pueden representar de la forma 1*h, donde h es un numero del conjunto de los números H.
Lo que nos pide el problema es encontrar a los semi-primos, que obtenemos al multiplicar a 2 primos.
Esto hay que realizarlo sobre los números del primos del conjunto H.

Lo primero que podemos hacer es generar los números del conjunto H con un 4n+1.
Una vez generados, procedemos a utilizar una criba, eliminando los números múltiplos de los números H.
Y finalmente realizar la multiplicación de parejas de H primos para obtener a los semi-primos del conjunto H.
Los primeros números H son los siguientes:

1, 5, 9, 13, 17, 21,25,29,33,37,41,45

Una vez calculados los números del conjunto H, podemos calcular a sus primos tachando los números que sean múltiplos de alguno.
Este principio es el que se utiliza en una Criba.
En la descripción del problema indica que 1 no es primo.

1, 5, 9, 13, 17, 21,25,29,33,37,41,45

En el ejemplo, solo se alcanza a observar como se eliminan los múltiplos de 5, pero es necesario eliminar a los múltiplos de 13, 17, 21, 29, etc.
Hay que notar que no tenemos que eliminar los múltiplos de 25 y 45, ya que automáticamente al eliminar los múltiplos de 5, se eliminan los múltiplos de 25 y 45.

Una vez obtenido el conjunto de los H primos, multiplicamos todas las parejas posibles de números para obtener el conjunto de los H semi-primos.

Los primeros H semi-primos son:
5 × 5 = 25
5 × 9 = 45
5 × 13 = 65
9 × 9 = 81
5 × 17 = 85

Para almacenarlos, podemos utilizar un set<int> o utilizar un arreglo y colocar en la posición de la multiplicación de los 2 números elegidos un 1, indicando que es un H semi primo.

La solucion al problema consiste en contar cuantos H semi-primos se encuentran en el intervalo 1 a N, incluyendo al N si llegara a ser un H semi-primo.

Código en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: