Help!
 

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 :confused: 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 ;)

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

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!

¿Español? :D

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

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

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

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

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;

Hola zeox, acerca de esto:
Te recomiendo que leas la Guía de Estilo, y el debate aquí planteado y entenderás el porqué de mi mensaje. ;)

Saludos!

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

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

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

// Saludos

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

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.

:D

// Saludos

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.

Hola:

Recapitulando un poco. Tomando los ejemplos que se han mostrado aquí y retocando algo, queda este código:

No vale incrementar i en 2, puesto que eso esquiva la prueba para algunos números que sí dan múltiplo.

pplus escribió:

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.


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

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:

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

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

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

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

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

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

Tambien tienes razón.

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

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

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

:D :eek: :eek: :D

Saludos cordiales

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

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)

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?