Hola:
Recapitulando un poco. Tomando los ejemplos que se han mostrado aquí y retocando algo, queda este código:
Código:
function EsPrimo(Num: Integer): Boolean;
var
temp, i : integer;
begin
i := 2;
result := TRUE;
while result AND (i < Num - 1) do
begin
temp := Num;
while Temp > 0 do Temp := Temp - i;
result := Temp < 0;
i := i + 1;
end;
end;
No vale incrementar i en 2, puesto que eso esquiva la prueba para algunos números que sí dan múltiplo.
pplus escribió:
Cita:
while Temp > i do Temp := Temp - i
resulta que restamos un numero [i] [x] veces. Y un numero n se puede expresar como n = i x + r . que es una division si lo escribimos asi:
n |__i___
r x (esto pretende ser un esquema de division)
|
Está claro que cualquier algoritmo simulará una división, puesto que lo que define a un número primo es que no sea divisible exacto salvo por 1. Pero de lo que se trata es de no emplear operadores de división.
Cita:
No encuentro ninguna diferencia entre hacer esta operacion y un desplazamiento de bits. Todo es dividir de una forma u otra. ¿estais de acuerdo conmigo?
...
Que opinais? ¿El algoritmo está mal de base?,
|
El algoritmo es bueno, pensé en un momento que habría alguna fórmula recursiva, pero no se me ocurre. Quizás una optimización sería que solo probáramos de restar con números ya primos (lo cual parece una optimización pero nos llevaría quizás mas tiempo el buscar esos números cada vez).
La cuestión es que no se deben utilizar operadores de división, ni /, ni sus variantes para números enteros (Div y Mod), pero tampoco "AND 1" ni "shr", que hacen lo mismo. De todas formas, estos operadores se utilizan para reducir el número de bucles, afectan al rendimiento, no a la validez del algoritmo, así que soy partidario de suprimirlos, no sea que eso le cueste la prueba.
Además, zeox dice que no tiene "ni P*** idea", creo que le conviene presentar un algoritmo que funcione pero que no parezca tomado de ningún foro.
Un saludo