0

Muy buenas, hace un par de meses me pusieron una práctica en mi universidad que trataba sobre hallar los primeros n numeros primos. Tenía habilitado Mooshak para ver si el código era eficiente y correcto pero ya ha cerrado el plazo. Aquí os dejo el código y si a alguien no le supone mucho trabajo darme algún consejo le estaría muy agradecido. Un saludo¡

 PROGRAM primos;  

CONST  
MAX=1000;  


TYPE  
TTachados=ARRAY[0..MAX] OF boolean;  
VAR  
tachados:TTachados;  


PROCEDURE primo(VAR tachados:Ttachados);  
VAR  
n,contar,numero,i,j:integer;  
r:real;  
BEGIN  
    FOR i:=1 TO MAX DO  
    tachados[i]:=FALSE;  
readln(n);  
numero:=0;  
j:=2;  
    REPEAT j:=j+2;     {Tachamos los múltiplos de dos}  
    tachados[j]:=TRUE;  
    UNTIL j> MAX;  
j:=3;  
    REPEAT j:=j+3;    {Tachamos los múltiplos de tres}  
    tachados[j]:=TRUE;  
    UNTIL j> max;    
i:=1;  
contar:=0;  
    REPEAT i:=i+1;  
    IF (tachados[i]=FALSE) THEN  {Escribimos los números que son primos mayores que 1}  
    BEGIN  
     writeln(i);  
     contar:=contar+1;  
    END;  
    UNTIL contar=n;  
readln();    
END;  


BEGIN         
primo(tachados);                             
readln();    

END
3
  • Bienvenido a Stack Overflow en español! Mira Cómo preguntar para que tu pregunta sea mejor recibida. También, aprovecha y haz el recorrido de bienvenida para entender mejor cómo funcionamos y de paso obtener tu primera medalla! Mas alla que esta pregunta no entra en su formato actual correctamente con la forma de funcionar del sitio, este algoritmo no devuelve numeros primos... Podrias explicar porque crees que este algortimo devuelve primos?
    – gbianchi
    Commented el 28 may. 2019 a las 23:43
  • ¿cuál es tu pregunta?
    – jachguate
    Commented el 30 may. 2019 a las 6:04
  • Estas almacenando en una tabla de booleanos , todos los números que no son primos , por lo tanto representará hasta n los que si son primos
    – Ángel
    Commented el 30 may. 2019 a las 9:22

1 respuesta 1

1

Vamos a la definición de número primo

En matemáticas, un número primo es un número natural mayor que 1 que tiene únicamente dos divisores distintos: él mismo y el 1.​ Por el contrario, los números compuestos son los números naturales que tienen algún divisor natural aparte de sí mismos y del 1, y, por lo tanto, pueden factorizarse. El número 1, por convenio, no se considera ni primo ni compuesto.

Entonces, para saber si un número es primo, básicamente debemos encontrar si tiene algún divisor que sea distintos del 1 y de si mismo. En otras palabras, basta con encontrar un divisor para saber que no es primo.

Para encontrar un divisor, la primera idea que usualmente viene a la mente es intentar dividirlo por todos los números menores a él, para ver si alguno resulta un divisor.

Sobre esta idea, se pueden realizar varias optimizaciones, pues al analizar con más detalle te das cuenta que no es necesario dividirlo por todos los números menores a él. De entrada, no hace falta intentar dividirlo por cualquier número compuesto, solo por los números primos.

Por ejemplo, si un número es divisible dentro de 15, que es un número compuesto, será divisible también entre los factores primos de 15, que son 3 y 5. Veamos 45, que es divisible entre 15, también es divisible entre 3 y es divisible entre 5.

Por otro lado, no va a existir ningún divisor que sea mayor a la mitad del número. Supongamos que estamos tratando de encontrar los divisores de 53. No va a haber ningún número arriba de 26 que pueda ser divisor de este, pues todos los resultados serán inferiores a dos y a medida que te acercas al número, vas aproximándote a 1. Veamos:

53/27 = 1.96296
53/28 = 1.89285
..
53/51 = 1.03922
53/52 = 1.01923

Con esto en mente, resulta sencillo hacer un programa. La idea básica es llevar una lista de los números primos que hemos encontrado e ir iterando entre los números buscando, para cada uno, si hay un divisor entre los primos que hemos encontrado antes.

Cada nuevo número primo que encontramos, lo vamos agregando a la lista y lo imprimimos.

La lista la inicializamos con el número 2, que es nuestro primer número primo conocido. A partir de allí, vamos probando solamente los números impares, pues de entrada sabemos que todos los números pares serán divisibles entre 2.

En código, esta idea luciría así:

program Primos;

{$APPTYPE CONSOLE}

{$R *.res}

uses
    System.SysUtils
  , Generics.Collections;

const
  LIMITE = 1000;
var
  NumerosPrimosEncontrados: TList<Integer>;
  NumeroEvaluar, Divisor: Integer;
  EsPrimo: Boolean;
begin
  try
    NumerosPrimosEncontrados := TList<Integer>.Create;
    try
      Writeln('Números primos');
      Writeln(2);
      NumerosPrimosEncontrados.Add(2);
      NumeroEvaluar := 3;
      while NumeroEvaluar <= LIMITE do
      begin
        EsPrimo := True;
        for Divisor in NumerosPrimosEncontrados do
        begin
          if Divisor > (NumeroEvaluar div 2) then
            break;
          if (NumeroEvaluar mod Divisor) = 0 then
          begin
            EsPrimo := False;
            Break;
          end;
        end;
        if EsPrimo then
        begin
          NumerosPrimosEncontrados.Add(NumeroEvaluar);
          Writeln(NumeroEvaluar);
        end;
        Inc(NumeroEvaluar, 2);
      end;
    finally
      NumerosPrimosEncontrados.Free;
    end;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  readln;
end.

La salida generada es la siguiente:

Números primos
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.