Generar numeros que contengan un numero dado x

[GoBrit]

Buenos días,

Estoy programando en C++ y tengo un problema que no puedo resolver.
Explico en que consiste:
Dado un numero inicial -> x he de generar números que contengan x hasta que uno de ellos sea primo, pero es importante que los numeros que genere sean en orden ascendente.
Ejemplo:
Si x = 7 el programa me retornara un 7, ya que es el primer numero que contiene 7 y es primo.
Si x = 001 generare el primer numero que contenga este valor y mirare si es primo, si no generare el siguiente, asi hasta encontrar un numero que contenga 001 y sea primo, en este caso el 3001 seria el primer numero que contiene x y es primo

No se si me explico muy bien, pero esta es la tarea que nos han encomendado.

Muchas gracias por cualquier ayuda.

[Orubatosu]

Dado el segundo ejemplo, supongo que la entrada puede contener cero a la izquierda, de manera que deberías de hacer la petición de ese dato como un string (o caracteres, a tu gusto) y antes de convertirlo a un tipo entero, comprobar si hay ceros a la izquierda. Si es el caso, añadir un "1" al principio del mismo, y convertirlo en entero.

A partir de ahi, crea una función que compruebe si un numero es primo (hay muchos ejemplos) y simplemente crea un bucle con un incremento de ese valor empezando por cero y que solo salga del bucle si se cumple la condición de que la función devuelve que es primo.

Básicamente tienes 3 cosas que hacer.

Una, la entrada de datos. Si es posible poner ceros a la izquierda, debes de hacer que la entrada de ese dato tenga eso en cuenta. Si pones un tipo int, esos ceros se descartarán, de ahí la idea de usar u string. Si hay ceros, añade un uno al principio.
Además, deberás de crear un pequeño programa o función que convierta ese string en un entero.

Dos, crea una función, yo la haría booleana que devuelve true si el numero entero que le pasas es primo

Tres y finalmente... simplemente en un bucle llama a la función para comprobar si el numero es primo, si no lo es, lo incrementas en uno y vuelves a empezar.

Supongo que hay otras formas, pero esta es bastante simple

[GoBrit]

El problema Orubatosu es que este método es poco eficiente. Necesito que sea lo mas eficiente posible y esos solo puede ser generando los números sucesivamente mas grandes a partir del que te dan que contenga el numero que te dan y después mirando si es o no primo.

Pero muchas gracias por el aporte.

[Gh057]

Hola GoBrit, porqué dices que es poco eficiente? si das una entrada y sobre ella debes obtener el primo más próximo... lo más intuitivo es ir incrementando en unidades.
Si fuera desde ese número hacia atrás puedes usar uan implementación de la criba de Eratóstenes... si te refieres con eficiente a intentar aplicar la frecuencia en la generación de número primos en la iteración (para no incrementar de uno en uno), bien puedes mirar lo publicado por Gauss o Riemann...
Pero no sé si sería correcto ya que podrías saltarte alguno, recuerda que son aproximaciones sobre la frecuencia en los números primos.

Si te refieres al algoritmo en sí, no tienes ninguno indicado por Orubatosu, hay muchos test de primalidad al respecto, entrando en juego el módulo de n.

Saludos

(agrego) si lo que intentas hacer es una función que te "genere" primos, desde un entero como piso, bueno... partiendo nuevamente de Riemann, hay todo un teorema llamado el teorema de Mills al respecto... pero entiendo que escapa a lo solicitado.

[GoBrit]

Gh057,

El problema esta en que no solo he de encontrar el numero primo mas próximo, sino que he de encontrar el numero primero mas próximo que contenga el que me dan inicialmente. Es decir si el numero inicial es 001 mi programa debe retornar 3001 que es el numero primo mas próximo y contiene 001. De la manera que propone Orubatosu el coste del algoritmo es lineal, ya que he de ir incrementando de uno en uno y mirar si es primero o no y si contiene el numero inicial o no.
Creo que la manera correcta y mas eficiente es generar los numeros que contienen 001 y mirar si son primeros. Por lo tanto si inicial = 001 el primer valor a comprobar es 1001, despues 2001, etc

Mi problema es que no se generar numeros sucesivamente mas grandes que contengan el valor inicial.

Muchas Gracias de nuevo!!

[Gh057]

Bueno, pero entonces si necesitas encontrar el primo más próximo que contenga a n sólo debes seguir la secuencia que indicaste, ya que los posibles primos intermedios deberían ser descartados al no tener n incluído en él...

- tomas la entrada n.
- es primo? no.
- generas un m que contenga a n (puedes utilizar la indicación de Orubatosu sobre cadenas)
- es primo? si. sales. sino, vuelves a generar otro m que contenga a n...

De aquí se desprende que tu iteración no debería estar definida por una sucesión lineal, sino por una condición booleana referida a la primalidad de m.

Saludos.

(agrego) recuerda que tu generación de m como indicaste es si tienes ceros adelante... si n tuviera un dígito distinto a cero como el de mayor peso, entiendo que deberías aumentar linealmente a la derecha; ya que ahí si podrías tener un posible número m, que contenga a n, que sea primo, y que estuviera más cerca...

[Orubatosu]

Un apunte, dije "incrementar en uno" genericamente, pero en realidad deberías de comprobar si el numero es impar, e incrementarlo siempre en 2, ya que ningún número par es primo (excepto el 2 claro).

[xustyx]

Este problema me suena a UDG. Tengo un amigo becario que ta de practicas donde trabajo y también lo estaba haciendo XD...

[Orubatosu]

Gh057,

El problema esta en que no solo he de encontrar el numero primo mas próximo, sino que he de encontrar el numero primero mas próximo que contenga el que me dan inicialmente. Es decir si el numero inicial es 001 mi programa debe retornar 3001 que es el numero primo mas próximo y contiene 001. De la manera que propone Orubatosu el coste del algoritmo es lineal, ya que he de ir incrementando de uno en uno y mirar si es primero o no y si contiene el numero inicial o no.
Creo que la manera correcta y mas eficiente es generar los numeros que contienen 001 y mirar si son primeros. Por lo tanto si inicial = 001 el primer valor a comprobar es 1001, despues 2001, etc

Mi problema es que no se generar numeros sucesivamente mas grandes que contengan el valor inicial.

Muchas Gracias de nuevo!!

Me temo que no te sigo...

Supongamos que el numero "x" es 001

Capturamos el dato como string, dado que el primer caracter es un "0", aplicamos un "1" antes. La cantidad de ceros es irrelevate, si el primer es un "0" el que haya mas no nos importa.

Lo convertimos a decimal (es algo relativamente sencillo, si no te aclaras con eso nos lo dices)

Suponiendo que fuera "001", el numero a partir del que buscar sería "1001"

Como 1001 no es primo, y dado que si le sumamos "1" perdemos esa condición de que "contenga 001" debes de probar incrementando el lado izquierda hasta 9, si no se da el caso, a partir de ahí y "contando hacia arriba" debes de recuperar nuevamente el 1001 y añadir una unidad a la derecha "10011" y a partir de ahí ya supongo que puedes ir añadiendo 2 en cada ciclo

Esto asumiendo que los ceros a la izquierda son significativos, en caso contrario la cosa cambia, ya que podemos hacer entonces algo diferente.

Dado que no sabemos la longitud de "x", no podemos aplicar reglas generales, y la "fuerza bruta" es una opción... simplemente añades 2 a cada ciclo y compruebas que el numero resultante contiene la secuencias que buscas, y que es primo.

Dado que la comprobación de si es primo es mas rápida, sería la que haría primero, la segunda sería comprobar si el numero en cuestión contiene "x" (que recordemos puede ser de una, dos o varias cifras). Para eso deberías de convertirlo en un string y comprobar si la cadena que buscas está dentro, algo sencillo, ya que string tiene una función para encontrar una cadena dentro de otra (find)

A todo esto, digo "es mas rápida" un poco de cabeza, quizás habría que hacer una comprobación para ver cual de las dos comprobaciones es mas rápida para ponerla primero a la hora de evaluar el número.

[GoBrit]

Correcto, todo lo que dices esta bien, hasta aquí mas o menos lo había deducido, pero y si el numero que te entran es 5678?¿ Entonces ya no funciona lo de añadir un 1 a la izquierda, incrementar-lo hasta que llegue a 9, después incrementar el de la izquierda, etc.

El problema no es determinar si es o no primero y si contiene o no el numero inicial dentro del otro, eso ya lo se hacer, el problema es encontrar una manera no lineal (incrementar de uno en uno, o de dos en dos) de generar el numero sucesivo al que nos dan y que lo contenga.

A continuación algunos ejemplos de lo que el programa debería devolver: (entrada->salida)
7->7
001->3001
007->4007
0123->20123
1109->1109
5678->56783

EXPLICACIÓN DE COMO DEBE FUNCIONAR EL PROGRAMA
Para acabar, supongamos que nos entran un 12. Nuestro programa debería comprobar si 12 es primero (no lo es), después encontraríamos el 112 (contiene 12) y miraríamos si es primo (no lo es), el numero siguiente es 120, que contiene 12 y tampoco es primo, así hasta el 127 que es el primer numero primo que contiene 12.

Esta explicación del funcionamiento ya la tengo implementada, pero no es lo mas eficiente posible, ya que incremento la variable inicial de 1 en 1. El problema es generar los números que contienen 12 de forma NO lineal.

Ya se que esta siendo complicado hacerme entender, pero la tarea que nos encomendaron no es nada fácil, disculpen las molestias y mi mala forma de hacerme entender, 

Muchísimas Gracias a todos los que me están ayudando.