Help!

[zeox]

Soy nuevo programando en este lenguaje, y tengo un gran problema. El miercoles necesito entregar un programa y no tengo ni P... idea de como plantearlo con Sentencias Repeat-Until o cualquiera de las variantes.

El Programa es el siguiente.

Determine si un numero "N" Entero y Positivo, leido como dato es o no un numero primo, sin emplear la multiplicacion, ni la división en ninguna de sus variantes, ni una funcion o procedimiento estandar de Turbo Pascal.


Si alguien logra realizar el programa, le agradeseria que me envie los Algoritmos a mi mail atomo_bg@hotmail.com

Thanks

[Julià T.]

Sin utilizar ninguna variante de división (ni "/" ni "div" ni "mod") lo único que se me ocurre es ir restando un número hasta que sea 0 o negativo

function esdivisiblepor(num, divisor):boolean;
begin
While Num>0 do Num:=Num-divisor;
//supongo que no se puede utilizar dec(num,divisor)
if Num=0 then Result:=True //es divisible por "divisor"
else result:=false;
end;

esdivisiblepor(10, 5) daria como resultado true
esdivisiblepor(49, 5) daria como resultado false

Ahora tan solo te queda emplar un bucle, para ir comprovando para cada divisor que sea necesario

[delphi.com.ar]

Hola zeox, te propongo que escribas la solución en el lenguaje que mejor conozcas, y seguramente muchos foristas, en los cuales me incluyo, van a estar gustosos de traducirla.

Saludos!

[roman]

Posteado originalmente por delphi.com.ar
Hola zeox, te propongo que escribas la solución en el lenguaje que mejor conozcas...

¿Español?

[marto]

function EsPrimo(Num: Integer): integer;
var
               temp, i, integer;
               enc: boolean;
begin
i := 2;
enc := false;
while (i < N - 1) and not Enc do begin
	temp := N;
	while Temp > 0 do Temp := N - i;
	if N = 0 enc := true;
	Inc(i);
end;
return Enc;
end;

No lo he probado, pero eso debería funcionar.

[marto]

Joer, estos problemas siempre me divirtieron, si te quieres quedar con tu profe preséntale esto:

function EsPrimo(Num: Integer): Boolean;
var
               temp, i, integer;
               enc: boolean;
begin
i := 3;
enc := N and 1 = 0;//es par
while (i < N - 1) and not Enc do begin
	temp := N;
	while Temp > 0 do Temp := N - i;
	if N = 0 enc := true;
	i := i + 2;
end;
return Enc;
end;

[zeox]

Bueno, las sugerencias estan muy buenas, voy a dapurar los posibles errores. Gracias.

P.D: Basicamente la lógica de programacion es igual en todos los lenguajes (incluyendo el Español jajaja) tu comentario no estuvo acertado Moderador. See u

[Julià T.]

La solución de marto, es muy buena, no le veo ningún fallo. Tan decir que 1 y 2 son primos (esto según criterio).

Releyendo creo que el 3 no le considera primo

[Julià T.]

ignorar mi respuesta anterior, se me ha ido la mano cuando estaba revisando el código de marto.

para solucionar, pongo el código depurado que incluye el dos como primo

function EsPrimo(N: Integer): Boolean;
var
temp, i: integer;
enc: boolean;
begin
i := 3;
enc := N and 1 = 0;//es par
while (i < N - 1) and not Enc do begin
temp := N;
while Temp > 0 do Temp := Temp - i;
if Temp = 0 then enc := true;
i := i + 2;
end;
result:=(not Enc) or (N=2);
end;

[delphi.com.ar]

Hola zeox, acerca de esto:

Posteado originalmente por zeox
tu comentario no estuvo acertado Moderador.

Te recomiendo que leas la Guía de Estilo, y el debate aquí planteado y entenderás el porqué de mi mensaje.

Saludos!

[pplu]

Si que se considera el 2 como primo en la sentencia

Enc := N And 1

Esto lo que hace es aplicar una máscara de bits al numero. Como en binario todos los numeros pares acaban en 0, Enc valdrá 0 si es par, y 1 si es impar.

y si quieres ahorrarte la mitad de vueltas en el bucle, puedes transformar:
while (i < N - 1) and not Enc do begin
en:
while (i < (N>>1)) and not Enc do begin

Esto divide N entre 2, ya que seguro que no habrá numeros que puedan dividir a n entre n/2 y n. El >> (right shift, o decalado) es un operador de C, seguro que delphi tambien lo tiene, pero no me acuerdo que pinta tenia. Es una division encubierta, pero válida.

Para hacerlo del todo chulo se podria ir hasta la raiz cuadrada de n (ya que hay una propiedad que dicta que n tiene todos los primos entre 2 y sqrt(n)). Pero no se hacer raices cuadradas de una forma mas o menos decente con las restricciones impuestas.

Seguiré pensando...

[pplu]

He mirado como era el decalado en Delphi/Pascal. la instruccion es shr (y shl tambien para el decalado a la izquierda)

asi que quedaria como (N shr 1) en vez de (N >> 1)

Salu2

[roman]

Posteado originalmente por pplu
while (i < (N>>1)) and not Enc do begin

Esto divide N entre 2...

Exacto, pero los requisitos originales indican que no se puede usar la división en ninguna de sus variantes.

// Saludos

[pplu]

No creo que desplazar a la derecha sea una variante de dividir... es simplemente desplazar los digitos en base 2, pero por esas casualidades de la vida... estamos dividiendo entre 2. Igual que si en decimal desplazas los digitos a la derecha una posicion: lo que consigues es dividir entre 10

Si lo miramos bien, en el fondo éste bucle esta dividiendo

while Temp > 0 do Temp := Temp - i

si lo escribimos asi (que es equivalente, pero que dá una vuelta menos, que ya de paso seria una optimizacion posible de este bucle)

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)

en el algoritmo perdemos x (que es el numero de vueltas que da el bucle), y temp acaba siendo r (que si es 0, hemos encontrado un multiplo), por lo que quieras que no, estas dividiendo de una forma encubierta.

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?

Otra pequeña optimización que nos ahorraria una vuelta en el bucle seria:

while Temp >= i do Temp := Temp - i;
if Temp = i then enc := true;

Esto nos ahorra una vuelta en caso de que el n sea divisible entre i.

Y aqui llegará la discusión ¿estamos dividiendo, o solo restando / desplazando bits?

Por la misma regla de tres, el (n and 1) tambien es dividir de una forma encubierta.
Solo estamos quitando los bits que son multiplos de 2 dentro del numero n (que son las posiciones 1 a 31 de un numero binario de 32 bits. Eso, a mi entender es dividir. Si lo queremos enfocar de otra manera, la operacion (N and 1) esta haciendo un (N mod 2). Y un mod es el resto de la división entera, por lo que tambien estamos dividiendo....

¿Que opinais? ¿El algoritmo está mal de base?, y ya por curiosidad... ¿alguien conoce algun metodo más sano (y mas optimo) de resolver el problema?

Salu2

[roman]

Como digas pplu. Me queda la curiosidad de ver qué dice el maestro en caso de que zeox decida utilizar tus argumentos ya que lo que de ellos se deduce es que la tarea es imposible.



// Saludos

[pplu]

Yo lo que entiendo del enunciado es que no dividas mi multipliques. Como variantes de division entiendo el div y el mod. Como variantes de multiplicacion entiendo la exponenciación. Quizas para el maestro lo que estamos haciendo es dividir (aunque no lo creo).

Tampoco creo que dados mis arguentos el problema sea imposible. Quizas solo estemos emperrandonos en querer dividir de formas alternativas sin pensar en otros metodos. Quizas solo lo hemos atacado el problema desde un angulo incorrecto.

[andres1569]

Hola:

Recapitulando un poco. Tomando los ejemplos que se han mostrado aquí y retocando algo, queda este 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ó:

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.

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

[pplu]

Andres, estoy de acuerdo con tu solucion. Es más academica y menos retorcida que la mia, pero tambien es mas lenta. Te comento la mia, que al final queda asi:

function EsPrimo(Num: Integer): Boolean;
var
               temp, i, integer;
               enc: boolean;
begin
Enc := (N and 1) = 0; //Aqui se dice si es divisible entre 2 y de paso se inicializa Enc
i := 3; // ya hemos comprobado los pares
while (i < (N shr 1)) and not Enc do begin //Aqui vamos hasta n/2
	temp := N;
	while Temp >= i do Temp := Temp - i; //Aqui "dividimos"
	enc := (Temp = i); //Es divisible por i
	i := i + 2;
end;
return Enc;
end;

y ya estaria la cosa resuelta

Comentarios: Si que se puede incrementar [i] de 2 en 2 porque antes ya has descartado todos los posibles multiplos de 2 con:
Enc := (n and 1) = 0

La mia es basicamente la tuya pero con las siguientes optimizaciones
- primero comprobar que sea multiplo de 2 (para asi poder incrementar i de 2 en 2)
- solo comprobar [i]s hasta n/2 (en ausencia de un sqrt(n)
- cambiar la condicion del while interno para que se ahorre una vuelta (y modificar la comprobacion de acuerdo con el cambio).

[pplu]

Y como ultima optimizacion que se me ocurre de momento es sacar una operacion que se mantiene invariante dentro del bucle

function EsPrimo(Num: Integer): Boolean;
var
               temp, i, hasta, integer;
               enc: boolean;
begin
Enc := (N and 1) = 0; //Aqui se dice si es divisible entre 2 y de paso se inicializa Enc
i := 3; // ya hemos comprobado los pares
hasta := N shr 1; // sacamos la condicion invariante
while (i < hasta) and not Enc do begin //Aqui vamos hasta n/2
	temp := N;
	while Temp >= i do Temp := Temp - i; //Aqui "dividimos"
	enc := (Temp = i); //Es divisible por i
	i := i + 2;
end;
return Enc;
end;

Sacando el (N shr 1) de la condicion del while, no se evaluará en cada vuelta del bucle, ahorrando asi, un poquito de tiempo (aunque los procesadores de hoy en dia ejecutan un shr en un ciclo...)
Algo es algo...

[Julià T.]

pplu no nos podemos olvidar del 2. A mí me eseñaron que el 2 era primo (también me eseñaron que el 1 era primo pero he sentido versiones para todos los gustos).

En cualquier casos creo que zeox deberia publicar el código que entregará al maestro y els resultado para quedarnos todos tranquilos