domingo, 31 de enero de 2016

Manejar archivos CSV con SQL

Como vimos anteriormente, los archivos CSV representan datos en forma de tabla. Las filas están separadas por saltos de línea y las columnas están separadas por comas o por punto y comas. Hoy vamos a usar el módulo DBI para acceder a los datos de estos archivos. El conjunto de herramientas DBI es una interfaz de acceso a distintas bases de datos, incluidas Oracle, Mysql y otros sistemas relacionales. La interfaz básica para consultar y actualizar la base de datos es el lenguaje SQL. El módulo DBI proporciona instrucciones SQL al módulo DBD::CSV, que a su vez pasa el control a otro módulo de interpretación de SQL.

Objetivo

Supongamos un sistema utilizado para registrar las consultas médicas. Una consulta médica tiene un archivo pacientes.csv con los datos personales de sus pacientes. Cada línea del archivo tiene el rut, el nombre y la edad de un paciente, separados por un símbolo ;. Así se ve el archivo:

12067539-7;Lorena López;32
15007265-4;Saúl Morales;26
8509454-8;Diego Muñoz;45
7752666-8;Gabriel Navarro;49
8015253-1;Darío Pacheco;51
9217890-0;Aldo Pimienta;39
9487280-4;Juan Rosas;42
12393241-2;Felipe Rubio;33
11426761-9;Samanta Pérez;35
15690109-1;José Ruiz;26
6092377-9;Alfonso Iúdica;65
9023365-3;Nancy Toledo;38
10985778-5;Tomás Valdés;38
13314970-8;Adán Vázquez;30
7295601-k;Wilson Muñoz;60
5106360-0;Alejandra Vega;71
8654231-5;Andrés Dib;55
10105321-0;Antonio Cabalgante;31
13087677-3;Walter Álvarez;28
9184011-1;Soledad Andrade;47
12028339-1;Jorge Bogado;29
10523653-0;Francisca Avaria;40
12187197-1;Felipe Mañas;36
5935556-2;Pablo Barriga;80
14350739-4;Eduardo Velo;29
6951420-0;Oscar Benítez;68
11370775-5;Hugo Leguizamón;31
11111756-k;Cristóbal Colón;34

Además, cada vez que alguien se atiende en la consulta, la visita es registrada en el archivo atenciones.csv, agregando una línea que tiene el rut del paciente, la fecha de la visita (en formato dia-mes-año) y el precio de la atención, también separados por ;. El archivo se ve así:

8015253-1;4-5-2016;69580
12393241-2;6-5-2016;57274
10985778-5;8-5-2016;73206
8015253-1;10-5-2016;30796
8015253-1;12-5-2016;47048
12028339-1;12-5-2016;47927
11426761-9;13-5-2016;39117
10985778-5;15-5-2016;86209
7752666-8;18-5-2016;41916
8015253-1;18-5-2016;74101
12187197-1;20-5-2016;38909
8654231-5;20-5-2016;75018
8654231-5;22-5-2016;64944
5106360-0;24-5-2016;53341
8015253-1;27-5-2016;76047
9217890-0;30-5-2016;57726
7752666-8;1-6-2016;54987
8509454-8;2-6-2016;76483
6092377-9;2-6-2016;62106
11370775-5;3-6-2016;67035
11370775-5;7-6-2016;47299
8509454-8;7-6-2016;73254
8509454-8;10-6-2016;82955
11111756-k;10-6-2016;56520
7752666-8;10-6-2016;40820
12028339-1;12-6-2016;79237
11111756-k;13-6-2016;69094
5935556-2;14-6-2016;73174
11111756-k;21-6-2016;70417
11426761-9;22-6-2016;80217
12067539-7;25-6-2016;31555
11370775-5;26-6-2016;75796
10523653-0;26-6-2016;34585
6951420-0;28-6-2016;45433
5106360-0;1-7-2016;48445
8654231-5;4-7-2016;76458

Note que las fechas están ordenadas de menos reciente a más reciente, ya que las nuevas líneas siempre se van agregando al final.

  • Escriba una función costo_total_paciente(rut) que entregue el costo total de las atenciones del paciente con el rut dado:

>>>Calcular el costo total del paciente 
Por favor, ingrese rut del paciente: 8015253-1
Costo total del paciente: 297572 

>>>Calcular el costo total del paciente 
Por favor, ingrese rut del paciente: 14350739-4
Costo total del paciente: 0


  • Escriba una función pacientes_dia(dia, mes, ano) que entregue una lista con los nombres de los pacientes que se atendieron el día señalado:

>>> Pacientes que se atendieron en una fecha dada
Por favor, ingrese el dia: 2
Por favor, ingrese el mes: 6
Por favor, ingrese el año: 2016
['Diego Muñoz', 'Alfonso Iúdica']
>>> Pacientes que se atendieron en una fecha dada
Por favor, ingrese el dia: 23
Por favor, ingrese el mes: 6
Por favor, ingrese el año: 2016
[]

  • Escriba una función pacientes_menores(edad) que construya un archivo CSV con los pacientes con edad <= a la edad dada.
Por ejemplo, el archivo jovenes.csv debe verse así:

>>>Pacientes menores a una edad dada
Por favor, ingrese la edad: 30
>>>jovenes.csv 
15007265-4;"Saúl Morales";26
15690109-1;"José Ruiz";26
13314970-8;"Adán Vázquez";30
13087677-3;"Walter Álvarez";28
12028339-1;"Jorge Bogado";29
14350739-4;"Eduardo Velo";29


Solución en Perl


#!/usr/bin/perl
use strict;
use warnings;
use DBI;
use Data::Dumper;
 
# el costo total de las atenciones del paciente con el rut dado
sub costo_total_paciente{
  my $rut= shift; 
  # conectamos 
  my $dbh= DBI->connect('DBI:CSV:');
  my $tabla= 'atenciones.csv';
  # seteamos el atributo sep_char para que use el separador ; en vez de ,
  $dbh->{csv_sep_char}= ";";
  # describimos los nombres de las columnas del archivo atenciones.csv
  $dbh->{csv_tables}{$tabla} = {
        col_names => [qw( rut fecha costo )]
        };
  # ejecutamos la consulta como un comando SQL
  my $query= "SELECT sum(costo) as costo_total FROM $tabla WHERE rut='$rut'";
  my $sth  = $dbh->prepare($query);
  $sth->execute();
  my $row = $sth->fetchrow_hashref;
  my $costo_total= 0;
  if ($row->{costo_total}){ $costo_total= $row->{costo_total}; }
  $sth->finish();
  return $costo_total;
}

print "Calcular el costo total del paciente \n";
print "Por favor, ingrese rut del paciente: ";
my $rut = <stdin>;
chomp($rut);
my $costo_total= costo_total_paciente($rut);
print "Costo total del paciente: $costo_total \n";

# listar los nombres de los pacientes que se atendieron el día dado
sub pacientes_dia{
  my ($dia, $mes, $anio)= @_;
  # conectamos 
  my $dbh= DBI->connect('DBI:CSV:');
  # seteamos el atributo sep_char para que use el separador ; en vez de ,
  $dbh->{csv_sep_char}= ";";
  # describimos los nombres de las columnas del archivo atenciones.csv
  my $atenciones= 'atenciones.csv';
  $dbh->{csv_tables}{$atenciones} = {
        col_names => [qw( rut fecha costo )]
        };
  # describimos los nombres de las columnas del archivo pacientes.csv
  my $pacientes= 'pacientes.csv';
  $dbh->{csv_tables}{$pacientes} = {
        col_names => [qw( rut nombre edad )]
        };
  # ejecutamos la consulta como un comando SQL
  my $fecha= join('-',$dia,$mes,$anio);
  my $query= "SELECT distinct rut FROM $atenciones WHERE fecha like '$fecha%'";
  my $sth  = $dbh->prepare($query);
  $sth->execute();
  while ( my $row = $sth->fetchrow_hashref ) {
    $query= "SELECT nombre FROM $pacientes WHERE rut='$row->{rut}'";
    my $sth2= $dbh->prepare($query);
    $sth2->execute();
    my $row2= $sth2->fetchrow_hashref;
    print $row2->{nombre} . "\n";
    $sth2->finish();
  }
  $sth->finish();
  return;
}

print "Pacientes que se atendieron en una fecha dada\n";
print "Por favor, ingrese el dia: ";
my $dia = <stdin>;
chomp($dia);
print "Por favor, ingrese el mes: ";
my $mes = <stdin>;
chomp($mes);
print "Por favor, ingrese el año: ";
my $anio = <stdin>;
chomp($anio);
pacientes_dia($dia, $mes, $anio);


# generar un archivo jovenes.csv con los datos de los pacientes menores a cierta edad dada
sub pacientes_menores{
  my $edad= shift;
  # conectamos 
  my $dbh= DBI->connect('DBI:CSV:');
  # seteamos el atributo sep_char para que use el separador ; en vez de ,
  $dbh->{csv_sep_char}= ";";
  # describimos los nombres de las columnas del archivo atenciones.csv
  my $pacientes= 'pacientes.csv';
  $dbh->{csv_tables}{$pacientes} = {
        col_names => [qw( rut nombre edad )]
        };
  # creamos la nueva tabla de menores
  my $jovenes= 'jovenes.csv';
  $dbh->do("CREATE TABLE $jovenes (rut CHAR(12), nombre CHAR(50), edad CHAR(3))")
  || die "No se pudo crear la tabla " . $dbh->errstr();
  # ejecutamos la consulta como un comando SQL
  my $query= "SELECT * FROM $pacientes WHERE edad < '$edad'";
  my $sth  = $dbh->prepare($query);
  $sth->execute();
  while ( my $row = $sth->fetchrow_hashref ) {
    $dbh->do("INSERT INTO $jovenes VALUES (".
      $dbh->quote($row->{rut}) . "," .
      $dbh->quote($row->{nombre}) . "," .
      $dbh->quote($row->{edad}) . ")")
      || die "No puedo insertar un registro, " . $dbh->errstr();
  }
  $sth->finish();
  
  return;
}

print "Pacientes menores a una edad dada\n";
print "Por favor, ingrese la edad: ";
my $edad = <stdin>;
chomp($edad);
pacientes_menores($edad);

viernes, 15 de enero de 2016

Archivos de texto CSV en Perl

Los archivos CSV representan datos en forma de tabla. Las filas están separadas por saltos de línea y las columnas están separadas por comas o por punto y comas.

Objetivo

Supongamos un sistema utilizado para registrar las consultas médicas. Una consulta médica tiene un archivo pacientes.csv con los datos personales de sus pacientes. Cada línea del archivo tiene el rut, el nombre y la edad de un paciente, separados por un símbolo ;. Así se ve el archivo:

12067539-7;Lorena López;32
15007265-4;Saúl Morales;26
8509454-8;Diego Muñoz;45
7752666-8;Gabriel Navarro;49
8015253-1;Darío Pacheco;51
9217890-0;Aldo Pimienta;39
9487280-4;Juan Rosas;42
12393241-2;Felipe Rubio;33
11426761-9;Samanta Pérez;35
15690109-1;José Ruiz;26
6092377-9;Alfonso Iúdica;65
9023365-3;Nancy Toledo;38
10985778-5;Tomás Valdés;38
13314970-8;Adán Vázquez;30
7295601-k;Wilson Muñoz;60
5106360-0;Alejandra Vega;71
8654231-5;Andrés Dib;55
10105321-0;Antonio Cabalgante;31
13087677-3;Walter Álvarez;28
9184011-1;Soledad Andrade;47
12028339-1;Jorge Bogado;29
10523653-0;Francisca Avaria;40
12187197-1;Felipe Mañas;36
5935556-2;Pablo Barriga;80
14350739-4;Eduardo Velo;29
6951420-0;Oscar Benítez;68
11370775-5;Hugo Leguizamón;31
11111756-k;Cristóbal Colón;34

Además, cada vez que alguien se atiende en la consulta, la visita es registrada en el archivo atenciones.csv, agregando una línea que tiene el rut del paciente, la fecha de la visita (en formato dia-mes-año) y el precio de la atención, también separados por ;. El archivo se ve así:

8015253-1;4-5-2016;69580
12393241-2;6-5-2016;57274
10985778-5;8-5-2016;73206
8015253-1;10-5-2016;30796
8015253-1;12-5-2016;47048
12028339-1;12-5-2016;47927
11426761-9;13-5-2016;39117
10985778-5;15-5-2016;86209
7752666-8;18-5-2016;41916
8015253-1;18-5-2016;74101
12187197-1;20-5-2016;38909
8654231-5;20-5-2016;75018
8654231-5;22-5-2016;64944
5106360-0;24-5-2016;53341
8015253-1;27-5-2016;76047
9217890-0;30-5-2016;57726
7752666-8;1-6-2016;54987
8509454-8;2-6-2016;76483
6092377-9;2-6-2016;62106
11370775-5;3-6-2016;67035
11370775-5;7-6-2016;47299
8509454-8;7-6-2016;73254
8509454-8;10-6-2016;82955
11111756-k;10-6-2016;56520
7752666-8;10-6-2016;40820
12028339-1;12-6-2016;79237
11111756-k;13-6-2016;69094
5935556-2;14-6-2016;73174
11111756-k;21-6-2016;70417
11426761-9;22-6-2016;80217
12067539-7;25-6-2016;31555
11370775-5;26-6-2016;75796
10523653-0;26-6-2016;34585
6951420-0;28-6-2016;45433
5106360-0;1-7-2016;48445
8654231-5;4-7-2016;76458

Note que las fechas están ordenadas de menos reciente a más reciente, ya que las nuevas líneas siempre se van agregando al final.

  • Escriba una función costo_total_paciente(rut) que entregue el costo total de las atenciones del paciente con el rut dado:

>>>Calcular el costo total del paciente 
Por favor, ingrese rut del paciente: 8015253-1
Costo total del paciente: 297572 

>>>Calcular el costo total del paciente 
Por favor, ingrese rut del paciente: 14350739-4
Costo total del paciente: 0


  • Escriba una función pacientes_dia(dia, mes, ano) que entregue una lista con los nombres de los pacientes que se atendieron el día señalado:

>>> Pacientes que se atendieron en una fecha dada
Por favor, ingrese el dia: 2
Por favor, ingrese el mes: 6
Por favor, ingrese el año: 2016
['Diego Muñoz', 'Alfonso Iúdica']
>>> Pacientes que se atendieron en una fecha dada
Por favor, ingrese el dia: 23
Por favor, ingrese el mes: 6
Por favor, ingrese el año: 2016
[]

  • Escriba una función pacientes_menores(edad) que construya un archivo CSV con los pacientes con edad <= a la edad dada.
Por ejemplo, el archivo jovenes.csv debe verse así:

>>>Pacientes menores a una edad dada
Por favor, ingrese la edad: 30
>>>jovenes.csv 
15007265-4;"Saúl Morales";26
15690109-1;"José Ruiz";26
13314970-8;"Adán Vázquez";30
13087677-3;"Walter Álvarez";28
12028339-1;"Jorge Bogado";29
14350739-4;"Eduardo Velo";29


Solución en Perl


#!/usr/bin/perl
use strict;
use warnings;
use Text::CSV;

print "Calcular el costo total del paciente \n";
print "Por favor, ingrese rut del paciente: ";
my $rut = <stdin>;
chomp($rut);
my $costo_total= costo_total_paciente($rut);
print "Costo total del paciente: $costo_total \n";

print "Pacientes que se atendieron en una fecha dada\n";
print "Por favor, ingrese el dia: ";
my $dia = <stdin>;
chomp($dia);
print "Por favor, ingrese el mes: ";
my $mes = <stdin>;
chomp($mes);
print "Por favor, ingrese el año: ";
my $anio = <stdin>;
chomp($anio);
pacientes_dia($dia, $mes, $anio);

print "Pacientes menores a una edad dada\n";
print "Por favor, ingrese la edad: ";
my $edad = <stdin>;
chomp($edad);
pacientes_menores($edad);

# el costo total de las atenciones del paciente con el rut dado
sub costo_total_paciente{
  my $rut= shift; 
  # seteamos el atributo sep_char para que use el separador ; en vez de ,
  # seteamos el atributo binary para acentos y eñes
  my $csv = Text::CSV->new ( { sep_char => ';', binary => 1 } )  
  or die "No puedo usar CSV: ".Text::CSV->error_diag ();

  my $costo_total= 0;
  open my $fh, "<:encoding(utf8)", "atenciones.csv" or die "atenciones.csv: $!";
  while ( my $row = $csv->getline( $fh ) ) {
    # si la primera columna concuerda con el rut dado, lo procesamos
    ($row->[0] eq $rut) or next; 
    $costo_total+= $row->[2];
  }
  $csv->eof or $csv->error_diag();
  close $fh;
  return $costo_total;
}

# listar los nombres de los pacientes que se atendieron el día dado
sub pacientes_dia{
  my ($dia, $mes, $anio)= @_;
  # seteamos el atributo sep_char para que use el separador ; en vez de ,
  # seteamos el atributo binary para acentos y eñes
  my $csv = Text::CSV->new ( { sep_char => ';', binary => 1 } )  
  or die "No puedo usar CSV: ".Text::CSV->error_diag ();

  my %pacientes;
  my $fecha= join('-',$dia,$mes,$anio);
  open my $fh, "<:encoding(utf8)", "atenciones.csv" or die "atenciones.csv: $!";
  while ( my $row = $csv->getline( $fh ) ) {
    # si la segunda columna concuerda con el dia dado, lo procesamos
    $row->[1] =~ m/^$fecha/ or next; 
    $pacientes{$row->[0]}= 1;
  }
  $csv->eof or $csv->error_diag();
  close $fh;
  listar_pacientes(keys %pacientes);
  return;
}
sub listar_pacientes{
  my (@pacientes)= @_;
  # seteamos el atributo sep_char para que use el separador ; en vez de ,
  # seteamos el atributo binary para acentos y eñes
  my $csv = Text::CSV->new ( { sep_char => ';', binary => 1 } )  
  or die "No puedo usar CSV: ".Text::CSV->error_diag ();

  open my $fh, "<:encoding(utf8)", "pacientes.csv" or die "pacientes.csv: $!";
  while ( my $row = $csv->getline( $fh ) ) {
    # si la primera columna concuerda con el paciente dado, lo procesamos
    $row->[0] or next;
    grep(/$row->[0]/,@pacientes) or next; 
    print $row->[1] . "\n";
  }
  $csv->eof or $csv->error_diag();
  close $fh;
  
  return;
}

# generar un archivo jovenes.csv con los datos de los pacientes menores a cierta edad dada
sub pacientes_menores{
  my $edad= shift;
  # seteamos el atributo sep_char para que use el separador ; en vez de ,
  # seteamos el atributo binary para acentos y eñes
  my $csv = Text::CSV->new ( { sep_char => ';', binary => 1 } )  
  or die "No puedo usar CSV: ".Text::CSV->error_diag ();

  my @menores;
  open my $fh, "<:encoding(utf8)", "pacientes.csv" or die "pacientes.csv: $!";
  while ( my $row = $csv->getline( $fh ) ) {
    # si la tercera columna es menor o igual a la edad dada, lo procesamos
    $row->[2] or next;
    ($row->[2]<=$edad) or next; 
    push(@menores,$row);
  }
  $csv->eof or $csv->error_diag();
  close $fh;
  
  $csv->eol ("\r\n");
  open $fh, ">:encoding(utf8)", "jovenes.csv" or die "jovenes.csv: $!";
  $csv->print ($fh, $_) for @menores;
  close $fh or die "jovenes.csv: $!";
  
  return;
}

viernes, 25 de diciembre de 2015

Serie de Fibonacci

Alejandro tiene un campo y su vecina, Selena, tiene una pareja de conejos. Selena quiere asociarse con Alejandro para la cría de conejos, le dice que en su campo pueden criarse juntos y multiplicarse. Le dice que al mes engendrarán una pareja de conejos y que esa pereja tardará un mes en engendrar otra pareja de conejos. A su vez la primer pareja seguirá engendrando parejas de conejos. Y así cada pareja de conejos seguirá teniendo parejas de conejos. Entonces Alejandro se pregunta: ¿Cuántos conejos tendrá al cabo de 12 meses? La respuesta está en la serie de Fibonacci.

Los números de Fibonacci Fk son una sucesión de números naturales definidos de la siguiente manera:
F0 = 0,
F1 = 1,
Fk = Fk−1 + Fk−2, cuando k≥2

En palabras simples, la sucesión de Fibonacci comienza con 0 y 1, y los siguientes términos siempre son la suma de los dos anteriores.



En la siguiente tabla, podemos ver los números de Fibonacci desde el 0-ésimo hasta el duodécimo.

n 0123456789101112...
Fn 01123581321345589144...


La sucesión puede utilizarse, de forma parecida, para contar el número de distintas rutas que puede seguir una abeja que va recorriendo las celdillas hexagonales de un panal.

Objetivo

Dado un número N obtener el número de Fibonacci n-ésimo.

La solución recursiva en Perl


La serie de Fibonacci puede definirse en forma recursiva, y es natural pensar una solución recursiva como eśta:

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

print "Serie Fibonacci\n";
print "Por favor, ingrese n: ";
my $n = <stdin>;
chomp($n);
my $valor= fibonacci($n);
print "El valor F($n) es $valor \n";

sub fibonacci{
  my $n= shift;
  # F0 = 0,F1 = 1,
  if ($n<=1){ return $n; }
  return fibonacci($n-1) + fibonacci($n-2);
}

Pero si estudiamos lo que pasa con éstas llamadas recursivas vemos que se llaman múltiples veces con los mismos argumentos. Esto es ineficiente, además las múltiples llamadas son exponenciales, por ejemplo fibonacci(5) llama a fibonacci(4) y fibonacci(3); pero fibonacci(4) también llama a fibonacci(3) y a fibonacci(2); pero cada fibonacci(3) llama a fibonacci(2) y así hasta llegar al caso base.

La solución con memoización en Perl

La solución más obvia es ir guardando los resultados parciales en un array para poder utilizarlos luego. Cada resultado parcial es la respuesta a un subproblema del problema inicial.

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

print "Serie Fibonacci\n";
print "Por favor, ingrese n: ";
my $n = <stdin>;
chomp($n);
my @serie;
$serie[0]= 0;
$serie[1]= 1;
my $valor= fibonacci($n);
print "El valor F($n) es $valor \n";

sub fibonacci{
  my $n= shift;
  if (defined($serie[$n])){ return $serie[$n]; }
  $serie[$n]= fibonacci($n-1) + fibonacci($n-2);
  return $serie[$n];
}


Uno podría pensar que la memoización es la manera más conveniente de resolver un problema de recursividad múltiple. Sin embargo, una función recursiva gasta un poco de memoria y tiempo en cada llamada recursiva. Por esta razón, la programación dinámica prescinde de la recursividad y resuelve el problema exclusivamente con la iteración.

La solución con programación dinámica en Perl

En general los pasos necesarios para resolver un problema con la programación dinámica son las siguientes:
  • Encontrar una definición recursiva para el problema (incluyendo los casos base)
  • Inicializar la estructura de memoria (normalmente un vector o una matriz)
  • Llenar el resultado para los casos base
  • Usar bucles para calcular el resultado para otros casos, empleando la definición recursiva (estrategia bottom-up)
La estrategia bottom-up consiste en resolver primero los subproblemas más pequeños, almacenar su solución, y luego resolver los problemas más complejos, usando los resultados almacenados.


La idea es llenar el vector o matriz de resultados de abajo arriba, empezando por los casos base. Al resolver un subproblema se aplica la misma idea recursiva para obtener el resultado. Sin embargo, si los subproblemas recursivos ya han sido resueltos no es necesario hacer ninguna llamada recursiva, sino que el resultado se puede calcular directamente a partir de los resultados guardados en memoria.

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

print "Serie Fibonacci\n";
print "Por favor, ingrese n: ";
my $n = <stdin>;
chomp($n);
my $valor= fibonacci($n);
print "El valor F($n) es $valor \n";

sub fibonacci{
  my $n= shift;
  my @serie;
  $serie[0]= 0;
  $serie[1]= 1;
  for (my $i= 2; $i <= $n; $i++){
    $serie[$i] = $serie[$i-2] + $serie[$i-1];
  }
  return $serie[$n];
}



viernes, 18 de diciembre de 2015

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