El dos no se me olvida:
Enc := (N and 1) = 0; //Aqui se dice si es divisible entre 2 y de paso se inicializa Enc Esto hace un (n mod 2) encubierto... que es lo mismo que comprobar que n es divisible entre 2 Lo he razonado en un reply arriba. |
Hola:
Faltan dos cosas, aparte de que devuelva también el 2 como primo: While Temp >= i ... debe cambiarse por while Temp > i ..., para que cuando sea Temp = i no siga decrementando, si no falla la sentencia siguiente. La última sentencia de la función debe ser result := NOT Enc (puesto que enc es TRUE si se ha encontrado un múltiplo). Con esto el algoritmo funciona perfectamente y es bastante bueno, lo de dividir por 2 el número de comprobaciones nadie lo discute, reduce el tiempo de resolución, sólo que el interesado nos puso algunas condiciones en el primer mensaje. Saludos |
Cita:
Cita:
Pues creo que ya tenemos una solucion bastante guapa Salu2 |
Bueno, gracias por todos sus comentarios, aqui les muestro los algoritmos que use para salucionar el problema.
Var A,B,C:longint; D:boolean; begin A:= strtoint(edit1.text); D:=False; for B:=2 to (A div 2) do Begin C:=A; Repeat C:=C-B; Until C<=0; if C=0 then D:=True; end; if D then label2.caption:='El Número no es Primo' else label2.caption:='El Número es Primo'; end; {Recuerden que soy nuevo en el Mundo de la Programación, soy estudiante de Ingeniería de Petróleo y también soy nuevo en el mundo de la programación.} //Thanks! ;) |
Lo siento zeox pero el div es una forma de división
|
Cuando Utilizo el operador Div lo estoy haciendo como condicion del contador del Ciclo, no para alla el numero primo como tal como tal
|
No creo que sea una respuesta válida, el enunciado excluye categóricamente el uso de la división, sin importar el uso de la misma.
No te parece algo así: Código:
function IsPrime(ANumber : Integer) : Boolean; |
En vez de hacer (n div 2) haz (n shr 1) son equivalentes a nivel funcional, y nadie se podra quejar que el shr es un derivado de la division
|
Me ha parecido un poco ofensivo que pusieras alli ese div despues de lo que se ha llegado a discutir en el foro :(
|
Como ultimo, y para comentar una variante cachonda (y posiblemente imposible a nivel físico), pero poco practica (a todos los niveles). Pero que demuestra que para optimizar en velocidad a veces has de "desoptimizar" en memoria ocupada....
// v sera un vector de booleanos v := [true, true, true, false, true, false, true, false, false, false, true, .......................................] EsEntero:= v[n - 1]; //tengamos en cuenta que las tablas empiezan en indice 0 Se puede tener una tabla estática de booleanos en la que cada posicion de la tabla representa si esa posición es prima. La longitud de la tabla es el rango máximo de un Integer Esta solucion no requiere dividir ni nada parecido... eso si... requiere tiempo... para picar la tabla ;) (Siento esta enorme ida de olla) ¿comentarios? |
pplu escribió:
Cita:
:D :eek: :eek: :D Saludos cordiales |
Cita:
|
para generar la tabla se requerirá una función para determinar si el numero es primo o no, por lo que volvemos al principio de todo, ... como calcular si un número es primo o no
por cierto ¿esta cadena de mensajes acabará en número primo ? |
Calcular si un numero es primo o no es lo más facil del asunto. Hay mil algoritmos más eficientes que el propuesto en el foro.
Incluso hay una función con la que es posible calcular el [n]esimo numero primo. (Aunque creo que está por demostrar, pero que funciona hasta numeros muuuuy gordos (estamos hablando de mas de 32 bits) Una función genera la tabla en forma de código de Pascal (yo sinceramente paso de inicializar la tabla cada vez que arranque el programa, porque seguramente se tarde muuucho). Ahora solo nos queda editar ese fichero y ponerle la funcion EsPrimo... Parece fácil, pero creo que hemos de pensar en la cantidad de datos que estamos manejando. Sobre el papel, y en la cabeza la cosa va bien... pero... Cuanto ocupa un Boolean en Deplhi? Ahora no lo recuerdo bien, pero os voy a exponer los posibles casos - 1 bit Esto es lo primero que se nos ocurre (pero tambien lo menos probable, ya que las memorias, como unidad mínima leen bytes (o grupos de bytes)) Tenemos que almacenar 2^32 booleanos dentro de la tabla por lo tanto 2^32 bits que ocupamos en memoria. 2^32 bits = 4294967296 4294967296 / 8 bits por byte = 536870912 bytes 536870912 bytes = 524288 KBytes 524288 KBytes = 512 MBytes No esta mal... eso solo es la tabla... pero de momento es posible... porque el codigo ocupa muy poco Ahora pongamonos en el caso de que un Booleano ocupara 1 Byte. Sacamos la 'calcu' y sorpresa! 4GBytes justos... Ni más ni menos... Esta cifra ya me suena fatidica... Nuestros queridos PC's pueden direccionar como máximo 4GB de memoria RAM. No nos queda espacio para el código (ni el SO):mad: Y ya no hablemos si son words (Enteros 16bits (2 bytes)) o dwords (Enteros de 32 bits (4 bytes)). Me direis: Como puede un booleano derrochar tantos bits cuando solo necesita uno? Pues facil... es más cómodo para nuestros procesadores leer un byte, word o dword que 1 bit de la memoria... porque la memoria solo transfiere bytes, words, o dwords y despues se ha de hacer la comprobacion del bit de la posición que toca Se que la palabra reservada packed sirve para comprimir estos booleanos de forma que no derrochen bits... pero no me acuerdo en que casos es aplicable... Por cierto... si alguien genera la tabla, que me la queme en CD, y me la envie :p Salu2 |
calculando los números primos que hay del 1 al 1.000.000 he encontrado 78500-1 (78499) los he dejado en
http://juliatorrijos.wanadooadsl.net/primos.rar |
Cuanto tardaste en generar todos estos primos?
Con que algoritmo? Salu2 |
Tarda unos 10 segundos en un portátil PIII celeron 1100
function TForm1.esprimer(Num: integer): boolean; Var Temp,Cont:integer; begin Result:=True; if Num in [1..2] then exit; if (num and 1)=0 then Result:=false; Temp:=Round(Sqrt(Num)); Cont:=3; while (Cont<=Temp) and Result do begin if (Num mod Cont)=0 then Result:=false; inc(cont,2); end; end; procedure TForm1.Button1Click(Sender: TObject); Var Min,Max,i:integer; begin memo1.Lines.Clear; Min:=StrToIntDef(Edit1.Text,1); Max:=StrToIntDef(Edit2.Text,1000000); memo1.Visible:=false; for i:=Min to Max do if EspRimer(i) then memo1.Lines.Add(inttostr(i)); memo1.Visible:=True; label1.Caption:=Inttostr(Memo1.Lines.count); end; |
Los matematicos mantienen un discusión "erudita" sobre la "Primalidad" del uno... ser primo o no ser primo...
pero indiscutiblemente el 2 es primo... siempre, toda la vida... es inconsebible decir que no lo es... |
la función que he realizado considera tanto al 1 como al 2 primos
|
Julià, ¿te atreves a generar todos los primos hasta el (2^32)-1?
A mi me da un poco de miedo porque el tiempo me parece que crece exponencialmente. Tendriamos que llegar al 4.294.967.295. Y solo hemos generado hasta el 1.000.000 Resulta que solo llevamos el 0,02% de la tabla hecha... Podriamos intentar con un algoritmo que fuera guardando los primos encontrados dentro de un array y ir dividiendo solo entre esos.. Podemos inicializar tranquilamente el array con el 2 y 3 en la primera y segunda posicion (ya vereis porque no meto al 1 en el saco) Código:
procedure EncuentraPrimos() Se que el codigo no es perfecto... lo he escrito tal y como me salia... y posiblemente haya mezclado lenguajes... pero creo que se entiende lo suficiente Intento recorrer la tabla de primos desde la posicion 0 hacia delante, porque me parece más probable que el numero que estemos probando sea divisible por los numeros más bajitos. Estais de acuerdo conmigo? He sacado el 1 fuera de la tabla de primos por razones obvias, y ya puestos podriamos sacar el 2, porque no vamos a caer nunca en numeros pares :) Y ya se que los arrays no son tan genersos... habria que redimensionarlo cada tanto en cuanto... yo lo haria de 1000 en 1000 posiciones de golpe... asi ahorramos tiempo precioso... y solo tenemos que hacer if (arrayPrimosLibre mod 1000 = 0) SetLength(arrayPrimos, arrayPrimosLibre + 1000); donde he puesto el (*) Si no, podemos intentar estimar el tamaño final que tendrá la tabla, y redimensionar en caso de "urgencia" Os gusta? |
La franja horaria es GMT +2. Ahora son las 01:31:03. |
Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi