Números primos

Primo o compuesto

Luis invitó a su primo Miguel a su casa. Mientras la mamá de Luis preparaba unas galletas caseras al horno para comer con la leche chocolatada, los primos revolvían unos libros de matemática y se encontraron con este teorema:

Para todo número primo p > 3, se tiene que p = 6k+1 ó p = 6k-1 

Luego de pensar un rato se dieron cuenta de que todos los números enteros pueden expresarse exactamente de un de las 6 posibles formas:
6k, 6k+1, 6k+2, 6k+3, 6k-2, ó 6k-1
-Claro! -dijo Luis- 6k es divisible por 6, por lo que no es primo.
-6k+2 es par, por lo que no es primo -agregó Miguel.
-6k-2 es par, así que tampoco es primo -se apuró a conjeturar Luis.
-Pero qué pasa con 6k+3?
-6k+3 es igual a 3(2k+1) que es divisible por 3, por lo que no es primo
-Por lo tanto, los números primos tienen que expresarse de la forma 6k+1 o 6k-1.
-Pero no todos los números de esa forma son primos, por ejemplo...
-Ya están las galletitas! A tomar la leche! -dijo la mamá.

Objetivo

Desarrolle un programa cuya entrada sea un entero positivo n, y cuya salida sea:

    primo, si el número es primo, y
    compuesto, si el número es compuesto.

Por ejemplo, si la entrada es 29, el programa debe decir primo. Si la entrada es 27, el programa debe decir compuesto.

Solución en Perl

#!/usr/bin/perl
use strict;
use warnings;

print "Por favor, ingrese un número mayor a 0: ";
my $n = <stdin>;
chomp($n);
if (primo($n)){ print "Primo!"; }
else{ print "Compuesto!"; }
print "\n";

sub primo{
  my $n= shift;
  if (1==$n){ return 0; }
  if (2==$n){ return 1; }
  if (3==$n){ return 1; }
  return teorema($n);
}
sub teorema{
  my $n= shift;
  my $resto= $n % 6;
  if (($resto != 1) && ($resto != 5)){ return 0; }
  my $raiz= sqrt($n);
  my $i= 1;
  while ((6*$i - 1) <= $raiz){
    if ( !($n % (6*$i + 1)) ){ return 0; }
    if ( !($n % (6*$i - 1)) ){ return 0; }
    $i++;
  }
  return 1;
}

Primeros m primos

Usando como base el programa diseñado en el ejercicio anterior, desarrolle otro programa que reciba como entrada un número entero positivo m y cuya salida sean los m primeros números primos.

Por ejemplo, si la entrada es 12, la salida del programa debe ser:

2
3
5
7
11
13
17
19
23
29
31
37

Solución en Perl

#!/usr/bin/perl
use strict;
use warnings;

print "Por favor, ingrese un número mayor a 0: ";
my $n = <stdin>;
chomp($n);
my $cantidad= 0;
my $i= 1;
while ($cantidad < $n){
  if (primo($i)){ print "$i\n"; $cantidad++; }
  $i++;
}
print "\n";

sub primo{
  my $n= shift;
  if (1==$n){ return 0; }
  if (2==$n){ return 1; }
  if (3==$n){ return 1; }
  return teorema($n);
}
sub teorema{
  my $n= shift;
  my $resto= $n % 6;
  if (($resto != 1) && ($resto != 5)){ return 0; }
  my $raiz= sqrt($n);
  my $i= 1;
  while ((6*$i - 1) <= $raiz){
    if ( !($n % (6*$i + 1)) ){ return 0; }
    if ( !($n % (6*$i - 1)) ){ return 0; }
    $i++;
  }
  return 1;
}

Primos hasta m

Modifique el programa del ejercicio anterior para que muestre los números primos menores o iguales a m.

Por ejemplo, si la entrada es 12, la salida debe ser:

2
3
5
7
11

Solución en Perl

#!/usr/bin/perl
use strict;
use warnings;

print "Por favor, ingrese un número mayor a 0: ";
my $n = <stdin>;
chomp($n);
my $i= 1;
while ($i <= $n){
  if (primo($i)){ print "$i\n"; }
  $i++;
}
print "\n";

sub primo{
  my $n= shift;
  if (1==$n){ return 0; }
  if (2==$n){ return 1; }
  if (3==$n){ return 1; }
  return teorema($n);
}
sub teorema{
  my $n= shift;
  my $resto= $n % 6;
  if (($resto != 1) && ($resto != 5)){ return 0; }
  my $raiz= sqrt($n);
  my $i= 1;
  while ((6*$i - 1) <= $raiz){
    if ( !($n % (6*$i + 1)) ){ return 0; }
    if ( !($n % (6*$i - 1)) ){ return 0; }
    $i++;
  }
  return 1;
}

 Más información

Un ejemplo de algoritmo eficiente y su explicación se puede encontrar en la Criba de Atkin