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

 

 


Tema destacado: Introducción a Git (Primera Parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  quien me ayuda con este programa!!!!numeros!!!
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: quien me ayuda con este programa!!!!numeros!!!  (Leído 4,032 veces)
akiss

Desconectado Desconectado

Mensajes: 2


Ver Perfil
quien me ayuda con este programa!!!!numeros!!!
« en: 4 Marzo 2012, 04:13 am »

La siguiente función determina si un número natural es primo.

int primo(long n)
{
   // si n es primo (asume sqrt() de math.h)
  
   int p = 1;  // si n es primo -asume si
   long d; // posibles divisores

   for (d = 2; d <= sqrt(n); d++)
       if (n % d == 0) p = 0;;

   if (n < 2) p = 0;

   return p;
}

El número 197 se dice que es un primo circular porque todas las rotaciones de sus dígitos, 197, 971 y 719, son a su vez primos.

¿Podría redactar una función que encuentre la cantidad de primos circulares menores que t? [Asuma e invoque la función primo().]


« Última modificación: 6 Marzo 2012, 01:41 am por akiss » En línea

Xandrete

Desconectado Desconectado

Mensajes: 210



Ver Perfil
Re: quien me ayuda con este programa!!!!numeros circulares primos!
« Respuesta #1 en: 4 Marzo 2012, 11:38 am »

Intenta algo. La premisa aquí es que no se hacen tareas. Si posteas alguna aproximación (aunque sea errónea) al problema, te ayudaremos. En el fondo, sólo necesitas una función que te sitúe el dígito de mayor peso de n en el lugar de las unidades. Inténtalo.

Por otro lado, te puedo decir que la función para detectar si un número es primo se puede mejorar. Sólo necesitas hacer el módulo por los números impares, una vez ya has comprobado que no es divisible por dos. De esta manera, te ahorras sqrt(n)/2 divisiones en el peor de los casos (que es que n sea efectivamente primo). Se puede optimizar más aún, teniendo en cuenta que a partir del 3 todo número primo p cumple que p = 6*k +- 1 para todo k perteneciente a los naturales. Por ejemplo, el 47 es primo y es igual al 6*8-1. El 37 es primo y es igual a 6*6 + 1. De este modo, el número de divisiones que realizas estará acotado por sqrt(n)/3. En un número primo de 8 cifras, la diferencia radica entre hacer unas 10000 divisiones (versión que has posteado), 5000 divisiones (versión que sólo comprueba con los divisores impares) y 3000 divisiones (la última versión que te he propuesto). Aproximadamente, por supuesto. Es sólo para que te hagas una idea.

Sin embargo, lo más óptimo si conoces la cota superior de n (el número máximo para el cual te van a preguntar si es primo o no) es el método conocido como criba de Eratóstenes (busca en la Wiki).

¡Saludos!


En línea

Xandrete

Desconectado Desconectado

Mensajes: 210



Ver Perfil
Re: quien me ayuda con este programa!!!!numeros circulares primos!
« Respuesta #2 en: 4 Marzo 2012, 19:49 pm »

Deberías dividir tu problema en subproblemas. De momento tienes aislada la parte para saber si un número es primo. Lo ideal ahora sería que pensaras en un módulo o función que te calculara la órbita de un número. Si lo integras todo en el main, el código será más difícil de leer y de corregir.

Aquí una propuesta de función:

Código
  1. int orbit(int n) {
  2. int n_10 = n/10;
  3. int orbit = n%10;
  4. n = n_10;
  5. while (n != 0) {
  6. orbit *= 10;
  7. n /= 10;
  8. }
  9. orbit += n_10;
  10. return orbit;
  11. }

Tu idea para obtener la "órbita" de un número (convirtiéndolo en una cadena y efectuando los desplazamientos correspondientes) es también válida.

Tu código es un poquitín chapuza por los siguientes motivos. Imagínate que evalúas el 23423426. Tu código comprueba la primera vez que no es primo, pero igualmente haces la rotación y vuelves a comprobar si es primo, y así 8 veces. Es evidente que si una sola de las órbitas del número  no es prima, el número no puede ser primo circular y puedes parar y pasar a evaluar el siguiente número. Además, si tienes 7777, harás 4 comprobaciones, cuando está claro que es totalmente innecesario (da igual las rotaciones que le apliques a 7777, seguirá siendo el mismo número y por tanto, basta con una sola comprobación. Y por último, si tienes que un número es primo circular, esta claro que todos los números de su órbita son primos circulares también, y cuando llegues a ellos no haría falta hacer todas las comprobaciones de nuevo. Aquí un código que he hecho para este mismo problema en que tengo en cuenta todo esto:

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. int k = 0;
  6.  
  7. int isPrime(int n) {
  8. int sqrt_n = (int) sqrt(n);
  9. int lim = (sqrt_n+1)/6;
  10. int i;
  11. if (n==2 || n==3) return 1;
  12. if (n==1 || !(n%2) || !(n%3)) return 0;
  13. for (i = 1; i <= lim; ++i) {
  14. if (!(n%(6*i-1)) || !n%(6*i+1)) return 0;
  15. ++k;
  16. }
  17. return 1;
  18. }
  19.  
  20. int orbit(int n) {
  21. int n_10 = n/10;
  22. int orbit = n%10;
  23. n = n_10;
  24. while (n != 0) {
  25. orbit *= 10;
  26. n /= 10;
  27. }
  28. orbit += n_10;
  29. return orbit;
  30. }
  31.  
  32. int main() {
  33. int n,prime,i,j,s,q;
  34. int* taken;
  35. scanf("%d",&n);
  36. taken = malloc(n*sizeof(int));
  37. for (i = 0; i < n; ++i) taken[i] = 0;
  38.  
  39. q = 1;
  40. for (i = 3; i < n; i += 2) {
  41. if (!taken[i]) {
  42. j = i;
  43. s = 0;
  44. do {
  45. if (j < n) {
  46. taken[j] = 1;
  47. ++s;
  48. }
  49. prime = isPrime(j);
  50. j = orbit(j);
  51. } while (prime && j!=i);
  52. if (prime) q += s;
  53. }
  54. }
  55. printf("%d\n",q);
  56. return 0;
  57. }
« Última modificación: 6 Marzo 2012, 19:46 pm por Xandrete » En línea

akiss

Desconectado Desconectado

Mensajes: 2


Ver Perfil
Re: quien me ayuda con este programa!!!!numeros!!!
« Respuesta #3 en: 6 Marzo 2012, 01:42 am »

muchas gracias mi broo!! de verdad
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines