numero primo

Introducción a la programación

Número primo

Enunciado
Definición
Especificación
Juego de pruebas
Versiones (correctas e incorrectas)
1

Introducción a la programación

Enunciado del problema
Escribir un módulo que determine si un número entero
positivo es primo o no.
Definición de número primo
Un número primo es un número natural que sólo es
divisible exactamente por sí mismoy la unidad.
¿1 es primo? Actualmente, se dice que no es primo,
aunque en ocasiones se considera que sí lo es.
¿X divisible por Y? : el resto de la división es 0
2

Introducción a la programación

Especificación

PRE ≡ { N > 0 }
módulo esprimo (ent N es entero) devuelve bool
POST ≡ { true si N es primo, false en otro caso}

3

Introducción a la programación

Juego de pruebas1

→ false

2

→ true

3

→ true

4

→ false

5

→ true

8

→ false

19

→ true

21

→ false

71

→ true

100

→ false
4

Introducción a la programación

Primera versión: explicación
• Contamos el número de divisores de 1 a N
• Si los divisores que hemos contado son 2,
entonces es primo; si es un número distinto, no
• (1 tendrá un divisor; el restode los que no son
primos, 3 o más)
• cont: contador: lleva la cuenta de los divisores del
número N que se han encontrado
• i: índice: indica todos los números entre 1 y N
5

Introducción a la programación

Primera versión: implementación
módulo esprimo (ent N es entero) devuelve bool
variables
cont es entero
//contador de divisores
i es entero
//índice para los naturales de 1 a Ninicio
cont ← 0
para i desde 1 hasta N hacer
si N % i == 0 entonces // si i es un divisor de N
cont ← cont + 1
finsi
si cont == 2 entonces
finpara
devolver true
si no
devolver (cont == 2) // sería equivalente
devolver false
fin
finsi
6

Introducción a la programación

Segunda versión: explicación
• Contamos el número de divisores
• No es necesario que el índice incluya 1 y elpropio N
• Si los divisores que hemos contado son 0,
entonces es primo; si es un número distinto, no
• ¡1 será primo!
• Deberá tratarse como un caso particular
7

Introducción a la programación

Segunda versión: implementación
módulo esprimo (ent N es entero) devuelve bool
variables
cont es entero //contador de divisores
i es entero
//índice para los naturales de 2 a N-1
inicio
siN == 1 entonces
devolver false
si no
cont ← 0
para i desde 2 hasta N-1 hacer
si N % i == 0 entonces // si i es un divisor de N
cont ← cont + 1
finsi
finpara
devolver (cont == 0)
finsi
fin

8

Introducción a la programación

Tercera versión: explicación
• No hace falta contar el número de divisores,
sólo saber si existen o no divisores
• haydivisor: variable booleana quedetecta si
hemos encontrado un divisor
• Inicialmente, haydivisor es falso
• i: indica todos los números entre 2 y N-1
• 1 se tratará como un caso particular

9

Introducción a la programación

Tercera versión: implementación
módulo esprimo (ent N es entero) devuelve bool
variables
haydivisor es bool
//detecta si se ha encontrado un divisor
i es entero
//índice para los naturales de 2a N-1
inicio
si N == 1 entonces
devolver false
si no
haydivisor ← false
para i desde 2 hasta N-1 hacer
si N % i == 0 entonces // si i es un divisor de N
haydivisor ← true
si no
haydivisor ← false
finsi
finpara
devolver (! haydivisor) // devolver (haydivisor==false)
finsi

10

Introducción a la programación

Tercera versión: implementación
módulo esprimo (ent N es entero)devuelve bool
variables
haydivisor es bool
//detecta si se ha encontrado un divisor
i es entero
//índice para los naturales de 2 a N-1
inicio
si N == 1 entonces
devolver false
si no
haydivisor ← false
para i desde 2 hasta N-1 hacer
si N % i == 0 entonces // si i es un divisor de N
haydivisor ← true
¡¡¡INCORRECTO!!!
si no
haydivisor toma un nuevo valor para cada i;
su valor final...