21 respuestas en este tema

[reethok]

Lo que pasa es que hice un programa sencillo que calcula si un número es primo o no... pero usando la variable LongInt solo se puede capturar un número que esté entre -2147483648 y 2147483648... y pues quisiera calcular números primos MUCHO más grandes...

Que variable podría utilizar que pueda almacenar números más grandes?

O cómo le podría hacer?

El código que llevo es este:

delphi

Program Primos;
 
  var
 
    numero : longint;
    contador : longint;
    interruptor: longint;
 
begin
 
writeln('Escribe el numero que deseas saber si es primo');
readln(numero);
 
  for contador := 2 to numero-1 do
   begin
   if numero mod contador = 0 then
   interruptor := 1;
   end;
if interruptor > 0 then
begin
  writeln(numero,' no es primo.');
  readln;
end
else
writeln(numero,' es primo.');
readln;
 
end.

De antemano muchas gracias! <Soy nuevo en el foro... y en Pascal... >

[Sergio]

No puedes hacer eso que quieres con variables de ningún tipo, la única manera es usar en todos tus calculos y variables llamadas a unas rutinas específicas de "precisión arbitrarias", que no vienen con delphi ni con lazarus.

Internamente es tratar a esas cantidades como arrays de digitos sin limite ninguno, y claro, todas las operaciones que vayas a hacerles han de cambiarse por llamadas a funciones que sepan tratar números en ese formato.

En esta web tienes una lista al respecto (primero hay una de criptografica y a continuacion otra de aritmetica de precision arbitraria): http://www.efg2.com/...ryptography.htm.

El segundo link empezando por el final parece ser el que te interesa, lleva incluso la busqueda de primos como ejemplo.

[seoane]

Solo dos cosas. La primera que para buscar un numero primo solo hay que probar si es divisible como máximo hasta su raíz cuadrada, es decir:

delphi

for contador := 2 to trunc(sqrt(numero)) do

Eso reducirá mucho la búsqueda.

Por otro lado ¿como de grandes son los números que buscas?

El tipo int64 te permite valores hasta 2^64=9223372036854775808
Y también tienes los TBCD que permite trabajar con números de hasta 20 cifras, aunque las operaciones son mas lentas

[Delphius]

Hola,

Tal vez reethok esté utilizando Longint porque proviene y/o quiere tener compatibilidad con Turbo Pascal.
Estoy de acuerdo con el consejo de Seoane. Lo que comenta Sergio lo veo como un caso extremo.

¿Cuál es el objetivo de esto? ¿Un ejercicio de alguna cátedra para la universidad o es para un desarrollo profesional, o personal que requiere un fino cuidado?

Si es para una materia me parece que con los consejos de Seoane basta y sobra.

Yo agregaría sólo una cosa, si el número ingresado ya de por si es par (mayor que 2) entonces puedes das por sentado de que el número no es primo. Recuerda que todo número primo es impar excepto el 2.

Si, además, la idea es generar una lista de primos (que es por lo general el verdadero problema que se suele pedir en cátedras) se puede diseñar una mejora: Un ciclo que recorra directamente sobre los números impares. 

Si es para algo profesional, y en verdad se busca trabajar número bien grandes yo diría que me parece algo excesivo el enfoque de hacer un ciclo sobre los divisores menor a su raíz. Tengo entendido que hay otros enfoques... como ciertos tests de primaridad. No sabría indicar muchas referencias, por lo pronto recomiendo la lectura del artículo en wikipedia.

Saludos,

[reethok]

No puedes hacer eso que quieres con variables de ningún tipo, la única manera es usar en todos tus calculos y variables llamadas a unas rutinas específicas de "precisión arbitrarias", que no vienen con delphi ni con lazarus.

Internamente es tratar a esas cantidades como arrays de digitos sin limite ninguno, y claro, todas las operaciones que vayas a hacerles han de cambiarse por llamadas a funciones que sepan tratar números en ese formato.

En esta web tienes una lista al respecto (primero hay una de criptografica y a continuacion otra de aritmetica de precision arbitraria): http://www.efg2.com/...ryptography.htm.

El segundo link empezando por el final parece ser el que te interesa, lleva incluso la busqueda de primos como ejemplo.

Vale... muchas gracias (aunque no entendí mucho Soy muy nuevo en Pascal y Lazarus)

Solo dos cosas. La primera que para buscar un numero primo solo hay que probar si es divisible como máximo hasta su raíz cuadrada, es decir:

delphi

for contador := 2 to trunc(sqrt(numero)) do

Eso reducirá mucho la búsqueda.

Por otro lado ¿como de grandes son los números que buscas?

El tipo int64 te permite valores hasta 2^64=9223372036854775808
Y también tienes los TBCD que permite trabajar con números de hasta 20 cifras, aunque las operaciones son mas lentas

Ohhh... muchas gracias por lo de la raíz cuadrada... probaré con int64 y TBCD... y ammm pensaba en algo tan largo como infinito... Cuando sepa un poco más (ya que soy nuevo) quiero hacer un pequeño programa para calcular números primos de Mersenne (ahora solo estoy practicando) y pues... El número primo de Mersenne más grande conocido tiene 12,978,189 cifras... así que... sí... necesito cifras muy grandes XD

Hola,

Tal vez reethok esté utilizando Longint porque proviene y/o quiere tener compatibilidad con Turbo Pascal.
Estoy de acuerdo con el consejo de Seoane. Lo que comenta Sergio lo veo como un caso extremo.

¿Cuál es el objetivo de esto? ¿Un ejercicio de alguna cátedra para la universidad o es para un desarrollo profesional, o personal que requiere un fino cuidado?

Si es para una materia me parece que con los consejos de Seoane basta y sobra.

Yo agregaría sólo una cosa, si el número ingresado ya de por si es par (mayor que 2) entonces puedes das por sentado de que el número no es primo. Recuerda que todo número primo es impar excepto el 2.

Si, además, la idea es generar una lista de primos (que es por lo general el verdadero problema que se suele pedir en cátedras) se puede diseñar una mejora: Un ciclo que recorra directamente sobre los números impares. 

Si es para algo profesional, y en verdad se busca trabajar número bien grandes yo diría que me parece algo excesivo el enfoque de hacer un ciclo sobre los divisores menor a su raíz. Tengo entendido que hay otros enfoques... como ciertos tests de primaridad. No sabría indicar muchas referencias, por lo pronto recomiendo la lectura del artículo en wikipedia.

Saludos,

Estoy usando LongInt porque es la variable que captura números más grandes que conozco... Y el objetivo de esto no es nada más que aprender... No voy aun en la universidad... pero me gusta la programación y leeí que Pascal es buen lenguaje para aprender primero... Después planeo aprender SmallTalk... después C y C++... pero bueno.

Muchas gracias a Todos!

[reethok]

Perdón por el multipost.

Ya cambie las variables LongInt por int64... y al compilar me da el siguiente error:

Error: Ordinal Expression Expected.

Eso en la linea que dice:

delphi

for contador := 2 to numero-1 do

Que puedo hacer?

Gracias!

[Delphius]

Hola reethok,
Algo tan grande como infinito no se puede, necesariamente tendrás que parar... 

Y hay dos formas, extremas, en que pares:
1. Generar un ciclo infinito que consuma todos los recursos
2. O que el número primo n-ésimo sea tan grande que debas reservar toda la memoria (o si quieres, en super extremo) que lo almacenes en disco y sea tan astronómicamente grande como para llenarlo todito todito  )

Considero que para practicar ya es suficiente, que lo importante es ir aprendiendo los conceptos y no tanto en si la sintaxis.

Para algo tan grande como lo que sugieres necesariamente deberás emplear bibliotecas de precisión arbitrarias como las que comenta Sergio. Básicamente la idea en que se basan es en reservar una porción de memoria lo suficientemente grande como uno quiera para almacenar el número dígito a dígito. Es como un enorme arreglo, array o vector donde cada posición es un dígito.
Esas bibliotecas ofrecen funciones y procedimientos para realizar operaciones elementales y avanzadas. No se valen de simples operaciones del tipo

delphi

var_resultado = operando1 + operando2;

Sino que hay una especie de API o un framework que permite realizar eso. Por ejemplo,

delphi

Add(var_resultado, Operando1, Operando2);

Luego este procedimiento Add implementará de manera eficiente (supuestamente, y en teoría) la suma.

Esas bibliotecas seguramente no son sencillas de utilizar. Deberás leer la documentación que ofrecen, hacer unas pruebas para interiorizarte de su funcionamiento.

El error que tienes se debe a que en el FOR no se permiten ciclos mayores a lo que permite el tipo ordinal. Como tu declaraste a contadorcomo Int64 y éste no es equivalente a los ordinales recibes ese error. No recuerdo bien como venía la mano pero creo que hay una función que permite pasar de Int64 a un ordinal.

Ya me fijo.

Saludos,

[Delphius]

Acabo de ver en la ayuda sobre el error y aclara justo lo que decía: un FOR sólo trabaja con un tipo ordinal.
Debes de cambiar el FOR por un REPEAT o un WHILE. Yo aconsejaría el REPEAT

Recuerdo que había una función para descomponer un Int64 en 2 integers: uno para la parte baja y otro para la alta. Pero esto no sirve para el caso.

Saludos,

[Sergio]

Hola reethook.

Si quieres morder los primos de Mersenne en pascal, C o cualquier lenguaje de programación "estandard", no tienes más remedio que usar rutinas de caclulo de precisión arbitraria, no tienes otra, con los tipos que te da el lenguaje no tienes ni para empezar en el mundo de los primos.

Mi consejo si quieres usar pascal: Bajate el link que te dije con rutinas y tipos especiales para calculos de precision arbitraria (mientras te quede memoria, claro, que en el caso que comentas podria ser un limite importante, los primos mas grandes usan varios teras solo para almacenarse, imagina para operar con varios de ellos) y mirate el ejemplo, modificarlo sera facil.

Mi segundo consejo: Busca un lenguaje especifico para matematicas, esos si que usan de fabrica enteros de longitud arbitraria: Mathematica es el más conocido, pero hay mas disponibles como MathLab, Mapple, etc.

Respecto de los consejos sobre como enfocar la busqueda, el de la raiz cuadrada es un clásico, lo de mirar solo impares es menos interesante: igual que descartas los divisibles por dos, podrias descartar por programa los divisibles por 3, 5, 7, 11... (ver si un numero es divisible por 2, 3, 5 y 11 es sencillo de programar) vamos, que complicando el codigo puedes usar trucos para acelerar la busqueda, pero el código al final deja de ser tan claro como debería.

[SistOpLinux]

Primer Método
Me parece recordar que si encontrabas un número N es primo por cualquier otro método (no por este), N+2 también es primo. Eso tendrás que verificarlo vos, pero de ser cierto te puede ayudar muchísimo. Bien puedo estar equivocado.

Segundo Método
Todos los números naturales se pueden dividir en una cadena de primos que multiplicados entre si dan el mismo número. Es lo que se denomina la "factorización" de un número. Aún los primos en si mismos, solo que en estos casos especiales, y con 1 excepción (justamente el 1), siempre tienen 2 factores: EL 1 y sí mismos.

Por lo tanto, cada vez que encuentres un número primo, ponlo un una lista. Luego, para determinar si un número es o no primo, solo tendrás que recorrer la lista dividiendo por cada uno de sus miembros. ¿Cual es el propósito de dividir un número entre 15?

Tanto Kylix, Delphi, como Lazarus contienen una serie de clases que podés utilizar para tu lista. Me parece que TurboPascal también la tiene, como parte de su librería Turbo Vision, pero no lo recuerdo. De modo que no te será necesario implementarla.

En General
Investiga más en Internet. Encontrarás aún más propiedades de los primos que te ayudarán a encontrarlos.

[jorgeu]

Para cálculo de precisión arbitraria he visto muy popular GMP http://gmplib.org

Por ahí vi una información algo vieja de un binding para pascal

http://gmplib.org/li...uly/001260.html

Espero les ayude

Saludos

[Delphius]

Primer Método
Me parece recordar que si encontrabas un número N es primo por cualquier otro método (no por este), N+2 también es primo. Eso tendrás que verificarlo vos, pero de ser cierto te puede ayudar muchísimo. Bien puedo estar equivocado.

Pues te confirmo, estás equivocado. Y tengo un ejemplo que no hace falta irse por grandes números: 19 y 21. El primero lo es, pero el segundo no. 

Lamento tirar abajo tu teoría.

Saludos,

[jorgeu]

Me puse a jugar con LISP y esto fue lo que salió

(defun lista-primos (min max)
 
  (defun primo(n)
  (let ((pp t ))
    (dotimes (i (- n 2) pp)
      (setf pp (and pp (> (mod n (+ i 2)) 0))))))

  (dotimes (i (- max min) nil)
    (if (primo i) (print (+ min i)))))

Listado de primos en un rango indicado. Método fuerza bruta jejejejejeje

Lo bueno es que LISP por definición tiene integrado el manejo de números de precisión arbitraria. Así que podemos pedir los primos entre 238752568127651928562367343278 y 12878237481725124818743257128914738794 sin problemas 

Acá una muestra

238752568127651928562367354677
238752568127651928562367354689
238752568127651928562367354701
238752568127651928562367354715
238752568127651928562367354721
238752568127651928562367354725
238752568127651928562367354745
238752568127651928562367354749
238752568127651928562367354761
238752568127651928562367354767
238752568127651928562367354769
238752568127651928562367354775
238752568127651928562367354781
238752568127651928562367354797
238752568127651928562367354805
238752568127651928562367354827
238752568127651928562367354829

[egostar]

La verdad es que no entiendo na' de na'

Me recuerda al famosísimo Interprete de Brainfucker

Salud OS

[jorgeu]

La verdad es que no entiendo na' de na'

Me recuerda al famosísimo Interprete de Brainfucker 

Salud OS

Pues me gusta más Whitespace por la seguridad. Si imprimes el programa nadie podrá decifrarlo 

[seoane]

Primer Método
Me parece recordar que si encontrabas un número N es primo por cualquier otro método (no por este), N+2 también es primo. Eso tendrás que verificarlo vos, pero de ser cierto te puede ayudar muchísimo. Bien puedo estar equivocado.

Pues te confirmo, estás equivocado. Y tengo un ejemplo que no hace falta irse por grandes números: 19 y 21. El primero lo es, pero el segundo no. 

Lamento tirar abajo tu teoría.

Saludos,

Si no recuerdo mal la conjetura decia que la suma de dos numeros primos, mayores de 2, mas 1 es muy probable, que no seguro, que sea primo.

Ej: 3+5+1=9
Ej: 13+23+1=37

[SistOpLinux]

Primer Método
Me parece recordar que si encontrabas un número N es primo por cualquier otro método (no por este), N+2 también es primo. Eso tendrás que verificarlo vos, pero de ser cierto te puede ayudar muchísimo. Bien puedo estar equivocado.

Pues te confirmo, estás equivocado. Y tengo un ejemplo que no hace falta irse por grandes números: 19 y 21. El primero lo es, pero el segundo no. 

Lamento tirar abajo tu teoría.

Saludos,

Está bien, Delphis, está bien.

También, no es como si confirmases que la "ley" de la conservación de la energía no lo es tal...

[SistOpLinux]

Primer Método
Me parece recordar que si encontrabas un número N es primo por cualquier otro método (no por este), N+2 también es primo. Eso tendrás que verificarlo vos, pero de ser cierto te puede ayudar muchísimo. Bien puedo estar equivocado.

Pues te confirmo, estás equivocado. Y tengo un ejemplo que no hace falta irse por grandes números: 19 y 21. El primero lo es, pero el segundo no. 

Lamento tirar abajo tu teoría.

Saludos,

Si no recuerdo mal la conjetura decia que la suma de dos numeros primos, mayores de 2, mas 1 es muy probable, que no seguro, que sea primo.

Ej: 3+5+1=9
Ej: 13+23+1=37

Gracias, Seoane. Eso bien pudo haber sido lo que yo mal recuerdo...

[SistOpLinux]

Reethok, en realidad estás tramando hacer un programa que maneje números de 8+ cifras, y en operaciones como el cálculo de la raíz cuadrada y las divisiones, multiplizaciones, y la factorización, dudo mucho que una simple PC te de abasto: a menos que quieras esperar unos cuantos (cientos de) siglos por tu resultado...

Pero podrías intentar hacer algo como lo que hizo el proyecto SETI@home. Dudo mucho que tengas tanto exito como ellos, pero deberías ser capaz de conseguir una supercomputadora moustruosa fácilmente.

Eso sí, te tomará mucho trabajo hacer semejante programa para el servidor mas la colección de clientes necesarios para todo tipo de plataformas...claro que Pascal te puede ayudar mucho aquí.

De este modo, podrías calcular tus primos tan grandes como quisieras...

[Delphius]

Me puse a jugar con LISP y esto fue lo que salió

(defun lista-primos (min max)
 
  (defun primo(n)
  (let ((pp t ))
    (dotimes (i (- n 2) pp)
      (setf pp (and pp (> (mod n (+ i 2)) 0))))))

  (dotimes (i (- max min) nil)
    (if (primo i) (print (+ min i)))))

Listado de primos en un rango indicado. Método fuerza bruta jejejejejeje

Lo bueno es que LISP por definición tiene integrado el manejo de números de precisión arbitraria. Así que podemos pedir los primos entre 238752568127651928562367343278 y 12878237481725124818743257128914738794 sin problemas 

Acá una muestra

238752568127651928562367354677
238752568127651928562367354689
238752568127651928562367354701
238752568127651928562367354715
238752568127651928562367354721
238752568127651928562367354725
238752568127651928562367354745
238752568127651928562367354749
238752568127651928562367354761
238752568127651928562367354767
238752568127651928562367354769
238752568127651928562367354775
238752568127651928562367354781
238752568127651928562367354797
238752568127651928562367354805
238752568127651928562367354827
238752568127651928562367354829

No menciones a esa cosa frente a mi presencia. Suficiente castigo recibí de su parte en Sistemas Expertos. El sólo hecho de pensar el CLIPS vienen de nuevo a mi cabeza los defrule, la elaboración de las reglas, el destinar días evaluando y probando a que todo se desencadene como debiera... Arrrggg  Si admito que me gustó la cátedra pero ese bicho me hizo gastar neuronas para cuando hice el proyecto final para la cátedra.

No sabía que tenía precisión arbitraria. Lo que uno aprende después de hace tiempo. 

Está bien, Delphis, está bien.

También, no es como si confirmases que la "ley" de la conservación de la energía no lo es tal...

No te vayas a las defensiva. Tampoco es que lo hice de malas. Sólo fue un comentario aclaratorio.

Saludos,