Help!

[pplu]

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.

[andres1569]

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

[pplu]

Posteado originalmente por andres1569
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.

Jejeje... pues si... muchos ojos (y cerebros) son mejor que uno

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.
[/b]

Tambien tienes razón.

Pues creo que ya tenemos una solucion bastante guapa

Salu2

[zeox]

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!

[Julià T.]

Lo siento zeox pero el div es una forma de división

[zeox]

Cuando Utilizo el operador Div lo estoy haciendo como condicion del contador del Ciclo, no para alla el numero primo como tal como tal

[delphi.com.ar]

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í:

function IsPrime(ANumber : Integer) : Boolean;
var
  iDiv,
  iTmp : Integer;
begin
  Result := True;
  for iDiv := 2 to ANumber - 1 do
  begin
    iTmp := ANumber;
    while iTmp > 0 do
      iTmp := iTmp - iDiv;
    if iTmp = 0 Then {Si el "Resto" es cero}
    begin
      Result := False;
      Break;
    end;
  end;
end;

Podrías optimizarlo agregando la comprobación del último Bit como te informaron anteriormente, y evitarías un procesamiento innecesario para los números pares.

[pplu]

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

[pplu]

Me ha parecido un poco ofensivo que pusieras alli ese div despues de lo que se ha llegado a discutir en el foro

[pplu]

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?

[andres1569]

pplu escribió:

Esta solucion no requiere dividir ni nada parecido... eso si... requiere tiempo... para picar la tabla

¿Picar la tabla? Se puede inicializar, recorriendo todos los integers y mirando si son primos; hay una decena de rutinas por ahí circulando que devuelven si un número es primo, la de Julián, la de pplu, la de Delphi.Com.Ar ..., la de zeox (lo malo de esta última es que emplea la instrucción Div pero a lo mejor eso da igual).



Saludos cordiales

[marto]

Posteado originalmente por andres1569
¿Picar la tabla? Se puede inicializar, recorriendo todos los integers y mirando si son primos;

Estoooooo andres, tu tienes muuuuuuuuuuuucha memoria en tu PC, no?

[Julià T.]

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 ?

[pplu]

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)

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

Salu2

[Julià T.]

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

[pplu]

Cuanto tardaste en generar todos estos primos?
Con que algoritmo?

Salu2

[Julià T.]

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;

[[gatosoft]]

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...

[Julià T.]

la función que he realizado considera tanto al 1 como al 2 primos

[pplu]

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)

procedure EncuentraPrimos()
arrayPrimos := [2,3];
arrayPrimosLibre := 2; 

For probando:=5 to 4294967295 step +2 do begin
i = 0
    while (arrayPrimos[i]<sqrt(probando)) And (not Divisible) do
        if (probando mod arrayPrimos[i] = 0) 
            Divisible: = true;
        else
            i++;
    end
    if not Divisible begin
        arrayPrimos[arrayPrimosLibre] = probando;
        arrayPrimosLibre++;
        (*)
    end
end

end;

Cuidado: Tenemos que usar unsigned integers. para llegar a (2^32)-1

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?