elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recuerda que debes registrarte en el foro para poder participar (preguntar y responder)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Problema simple con programa números primos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Problema simple con programa números primos  (Leído 4,240 veces)
jamatbar

Desconectado Desconectado

Mensajes: 100


Ver Perfil
Problema simple con programa números primos
« en: 10 Agosto 2014, 03:00 am »

Buenas, aquí estoy empezando con C++ y tengo una duda con un ejercicio de una práctica de la facultad.

Tengo un programa (muy rudimentario) que tengo que ir mejorando poco a poco, el programa me dice si un número no es primo y si sí es primo sale del programa, este es el código:

Código:
#include <stdio.h>

#define RESPUESTANOPRIMO " %d no es primo\n"
#define RESPUESTAPRIMO   " %d es primo\n"

int main()
{
  /* Almacenara el numero leido por teclado */
  int valor;
  /* Servira como indice del bucle for que vamos a utilizar. */
  int i;
  /* Solicitamos el numero que queremos saber si es primo */
     printf("Introduzca un valor: ");
     scanf(" %d", &valor);
     
/* El bucle lo comenzamos en 2: todo numero es divisible por 1
* y lo terminamos antes de valor: todo numero es divisible por si mismo */

for ( i = 2; i < valor; i++ )
     if (0 == (valor % i))
     /* Si el resto es cero, es porque i divide
     * No es primo. */
     printf(RESPUESTANOPRIMO, valor);
 
  return 0;
}

Y me pide que una vez comprobado que el dos no es divisor, probar sólo con los números impares.

Yo creo que debo cambiar ese i++ por un i+=2, para que desde el 3 todas las demás comprobaciones se hagan con números impares, pero no sé como inicializar la variable i en el 3 después de la primera "pasada" del bucle for. Lo que he hecho es esto:

Código:
#include <stdio.h>


#define RESPUESTANOPRIMO    "%d no es primo\n"
#define RESPUESTAPRIMO      "%d es primo\n"



int main()
{
  /* Almacenara el numero leido por teclado */
  int valor;
  /* Servira como indice del bucle for que vamos a utilizar. */
  int i;

  /* Solicitamos el numero que queremos saber si es primo */
  printf("Introduzca un valor: ");
  scanf("%d", &valor);

  if (valor == 2);

  else

    {
      if (0 == (valor % 2))


/* Si el resto es cero, es porque i divide  a numero:
* No es primo. */
        printf(RESPUESTANOPRIMO, valor);
      else
        {
          for (i = 3; i < valor; i += 2)
            if (0 == (valor % i))
              /* Si el resto es cero, es porque i divide a numero:
               * No es primo. */
              printf(RESPUESTANOPRIMO, valor);
        }

    }

  return 0;
}

Que hace lo que quiero pero no creo que deba sacar el 2 "a lo bruto" del bucle for, ¿alguna ayuda?

No hace falta mejorar el programa, sólo hacer dicha modificación para luego poder hacer otros apartados que me piden.

Gracias de antemano y un saludo!


En línea

engel lex
Colaborador
***
Desconectado Desconectado

Mensajes: 15.347



Ver Perfil
Re: Problema simple con programa números primos
« Respuesta #1 en: 10 Agosto 2014, 04:16 am »

normalmente por la inconveniencia que presenta el 2 como par-primo si se saca del bucle, recomiendo el i nada más recorrerlo hasta la raíz del numero ingresado, ya que más allá de la raíz estarías repitiendo divisores ya que ese es el factor donde pivotan los valores

ej
Código:
210 (raíz ~14.5)
=1*210
=2*105
=3*70
=5*42
=6*35
=7*30
=10*21
=14*15 (aquí está el pivote, a partir de aqui serán las mismas cuentas invertidas)
=15*14
=21*10
...(etc)

entonces ejemplo, para saber si 211 (raíz ~14.5) es primo solo basta con probar 2, 3, 5, 7, 9, 11, 13 según tu algorimo y solo probarías 7 factores en lugar de 211 dandole mucha velocidad...

y por lo menos 3.123.133 en lugar de probar más de 1millon de factores, solo pruebas unos 884 factores y listo...


En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
Blaster

Desconectado Desconectado

Mensajes: 190


Ver Perfil
Re: Problema simple con programa números primos
« Respuesta #2 en: 10 Agosto 2014, 05:26 am »

Otra forma de reducir exponencialmente el número de iteraciónes es la siguiente:

Código
  1. for (i = 3; i * i <= valor; i += 2)


Saludos   
En línea

engel lex
Colaborador
***
Desconectado Desconectado

Mensajes: 15.347



Ver Perfil
Re: Problema simple con programa números primos
« Respuesta #3 en: 10 Agosto 2014, 05:29 am »

Otra forma de reducir exponencialmente el número de iteraciónes es la siguiente:

Código
  1. for (i = 3; i * i <= valor; i += 2)


Saludos   

justamente lo que explicaba, aunque siempre olvido para la raíz usar este método!
En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Problema simple con programa números primos
« Respuesta #4 en: 10 Agosto 2014, 09:13 am »


entonces ejemplo, para saber si 211 (raíz ~14.5) es primo solo basta con probar 2, 3, 5, 7, 9, 11, 13 según tu algoritmo y solo probarías 7 factores en lugar de 211 dándole mucha velocidad...

y por lo menos 3.123.133 en lugar de probar más de 1 millón de factores, solo pruebas unos 884 factores y listo...

Eso último no está nada claro, si el número es 1 millón habría que probar según tu propuesta hasta num*num = 1000 000 , es decir de 3 a num=999 (1000).

Pero aún así se estaría trabajando en balde ya que probaríamos, entre otros, 15, 25, 27, 33, 35, 45, 49, ......que sería una redundancia ya que si  es divisible entre 3 y 5 el probar con 15 está de más y así sucesivamente.

Es decir, tan sólo hay que probar con divisores que, además de ser impares, sean primos, es decir:

3 , 5 , 7, 11 , 13 , 15 , 17 , 19 , 21 , 23 , 25 , 27  , 29 ,31 ,   33  ,   35 , 37 , 39 , 41 , 43 , 45 , 47 ,   49 ......

En el caso de 1000 000 hasta num = 1000 ( 1000*1000=1000000) hay en principio que tomar los impares, que son 500. Pero de ellos tan sólo hay 168 primos con lo que ya reducimos considerablemente el número de probaturas.

Y en el caso de 100 000 0000 hay ¡¡¡ "50 000 000" ¡¡¡ de impares pero tan solo 5 761 455 primos, con lo que ahorramos las pruebas en un factor de casi 20.

Por lo que de una forma simple se pueden ir guardando los primos obtenidos en un array, "primos", e ir probando sólo a estos en lugar de todos los impares, algo como:

Código
  1.  for ( primos[k] ; prims[k] * primos[k] <= n ; k++ ) {
  2.      if ( n % primos[k] == 0 )

¡¡¡¡ Saluditos! ..... !!!!


« Última modificación: 10 Agosto 2014, 09:27 am por leosansan » En línea

engel lex
Colaborador
***
Desconectado Desconectado

Mensajes: 15.347



Ver Perfil
Re: Problema simple con programa números primos
« Respuesta #5 en: 10 Agosto 2014, 09:35 am »

Eso último no está nada claro, si el número es 1 millón habría que probar según tu propuesta hasta num*num = 1000 000 , es decir de 3 a num=1000.

no entendí lo que no estaba claro D: pero extiendo

en lugar de probar de 2 en 2 desde 3 hasta 3.123.133 (dando unos 1,5millones de ciclos) se haría desde 3 durante i*i <= 3.123.133 siendo unos 884 ciclos si no me equivoco...

lo que tu dices de saltar todos los otros factores no me parece una buena idea, porque implicaría almacenar en memoria todos los factores intermedios y evaluarlos creando un ciclo secundario... siento que se haría un motón de operaciones de modulo extra en lugar de simplemente el modulo del numero que si falla es uno solo y listo...

o por lo menos que entendí de tí sería algo como esto...


Código
  1. for (i = 3; i * i <= valor; i += 2){
  2.    for ( primos[k] ; prims[k] * primos[k] <= n ; k++ ){
  3.        if ( n % primos[k] == 0 ) //ir con el siguiente i
  4.    }
  5.    //si no saltó almacenar i en arreglo
  6.  


-----sigo agregando-----

la cantidad original de modulos a ejecutar era
n/2-3

yo lo indico llevar a
sqrt(n)/2-3

tu lo estás llevando a
(n-3)*k!
donde k es la cantidad de primos intermedios :s (ya que serían 2 ciclos haciendo mods y el segundo creciendo en cada vuelta de n)

incluso pensé hace tiempo que podría hacerse
Código
  1. for (i = 3; i * i <= valor; i += 2){
  2.    if(i%3==0) continue;
  3.    if(i%5==0) continue;
  4.  
porque "aumenta" la eficiencia en ~20% pero no, ya que al final en el mejor de los casos hace 1 mod (si es multiplo de 3), y en el peor hace 3 mods, sabiendo que en este ciclo la operacion más pesada es el mod y es igual en tiempo para %3 y  %3.000.000, entonces no vale la pena el procesamiento extra
« Última modificación: 10 Agosto 2014, 09:53 am por engel lex » En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
ivancea96


Desconectado Desconectado

Mensajes: 3.411


ASMático


Ver Perfil WWW
Re: Problema simple con programa números primos
« Respuesta #6 en: 10 Agosto 2014, 13:04 pm »

El problema de guardar un array de primos, es para números mayores a un millardo. Ahí podría empezar a consumir hasta un GB de memoria.
En línea

leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Problema simple con programa números primos
« Respuesta #7 en: 11 Agosto 2014, 06:34 am »

no entendí lo que no estaba claro D: pero extiendo
.............................................................

Está claro que no me exprese bien, sorry!!!.

Yo no hablaba del caso de comprobar si "un" número concreto es o no primo sino de calcular  los números primos en un intervalo, como de 1  10^8, por ejemplo. Está claro que si sólo es un número es casi impepinable usar el método del módulo, y aún así se pueden introducir mejoras.

En cuanto al número de operaciones es al menos menor ya que lo único que se hace es sustituir la operación de "i*i<N" por "primos[ i ]*primos[ i ]<N". El motivo de que sea menor es que en el método del "i*i" se usan todos los impares desde 3 a la raíz del número en el peor de los casos, como en el caso de querer comprobar si 99991 es o no primo, sin embargo en el método del array sólo se usan los primos previamente  calculados que obviamente son menores que los impares. La única penalización es el uso de un array y que tampoco ya que lo que procede realmente es ir guardando los primos calculados en en fichero y escribir y leer los cuando proceda. Como ves, se consigue disminuir el número de operaciones módulo en unos cuantos miles, todo lo cual redunda en una mejora, al menos sobre el papel.

No obstante, y para que no digan que hago tareas, será en este otro hilo, cortesía de ivancea96 aporte_detector_de_numeros_primos_en_c donde podrás encontrar una comparativa de los métodos y donde se pone de manifiesto la bondad del método del uso de "primos" frente al "i*i"

Espero que ahora esté más claro.



Un fuerte saludo de León amigo engel lex.


« Última modificación: 11 Agosto 2014, 07:59 am por leosansan » En línea

engel lex
Colaborador
***
Desconectado Desconectado

Mensajes: 15.347



Ver Perfil
Re: Problema simple con programa números primos
« Respuesta #8 en: 12 Agosto 2014, 01:12 am »

Está claro que no me exprese bien, sorry!!!.

Yo no hablaba del caso de comprobar si "un" número concreto es o no primo sino de calcular  los números primos en un intervalo, como de 1  10^8, por ejemplo. Está claro que si sólo es un número es casi impepinable usar el método del módulo, y aún así se pueden introducir mejoras.

En cuanto al número de operaciones es al menos menor ya que lo único que se hace es sustituir la operación de "i*i<N" por "primos[ i ]*primos[ i ]<N". El motivo de que sea menor es que en el método del "i*i" se usan todos los impares desde 3 a la raíz del número en el peor de los casos, como en el caso de querer comprobar si 99991 es o no primo, sin embargo en el método del array sólo se usan los primos previamente  calculados que obviamente son menores que los impares. La única penalización es el uso de un array y que tampoco ya que lo que procede realmente es ir guardando los primos calculados en en fichero y escribir y leer los cuando proceda. Como ves, se consigue disminuir el número de operaciones módulo en unos cuantos miles, todo lo cual redunda en una mejora, al menos sobre el papel.

No obstante, y para que no digan que hago tareas, será en este otro hilo, cortesía de ivancea96 aporte_detector_de_numeros_primos_en_c donde podrás encontrar una comparativa de los métodos y donde se pone de manifiesto la bondad del método del uso de "primos" frente al "i*i"

Espero que ahora esté más claro.



Un fuerte saludo de León amigo engel lex.




ahora si te comprendí en ese ejemplo si es muy bien aplicable la idea! :P
En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Problema simple con programa números primos
« Respuesta #9 en: 12 Agosto 2014, 05:29 am »

ahora si te comprendí en ese ejemplo si es muy bien aplicable la idea! :P

Siento no haberme explicado con claridad la primera vez. Gracias por la comprensión.

Un fuerte saludo de León.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Ayuda con Programa numeros primos matriz
Java
Jaime1315 7 8,318 Último mensaje 9 Febrero 2013, 13:58 pm
por Mitsu
[JS] ¿Programa para calcular números primos?
Scripting
Linton 5 16,686 Último mensaje 23 Julio 2013, 07:40 am
por Linton
Problema con programa para hallar numeros primos
Programación C/C++
Caster 6 2,894 Último mensaje 24 Mayo 2014, 19:04 pm
por leosansan
Por favor ayuda con un programa en C, números primos « 1 2 »
Programación C/C++
rod89 10 4,027 Último mensaje 9 Noviembre 2014, 17:31 pm
por daryo
Hacer un programa con DEV C++ de números primos.
Programación C/C++
divadrn 3 11,681 Último mensaje 11 Noviembre 2014, 13:23 pm
por Eternal Idol
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines