Skip to content
ExamplesEspañolWorkspace →

Prime Numbers

Finds every prime number up to a limit.

Level
Intermediate
Topic:
Math
Concepts:
Input & output
Functions
Mientras
Para
Math
Open in Codoritmo

Run, change and debug this example in your browser.

What you'll learn

The EsPrimo Funcion returns a Logico and uses MOD to look for divisors. Its Mientras loop stops early, past the square root or as soon as a divisor turns up.

Code

primes.psc · 29 lines
Funcion primo <- EsPrimo(n)    Definir primo Como Logico    Definir divisor Como Entero    primo <- n > 1    divisor <- 2    // Basta con probar divisores hasta la raíz cuadrada de n    Mientras primo Y divisor * divisor <= n Hacer        Si n MOD divisor = 0 Entonces            primo <- Falso        FinSi        divisor <- divisor + 1    FinMientrasFinFuncionAlgoritmo NumerosPrimos    Definir limite, n, contador Como Entero    Escribir "¿Hasta qué número busco primos?"    Leer limite    contador <- 0    Escribir "Primos hasta ", limite, ":"    Para n <- 2 Hasta limite Hacer        Si EsPrimo(n) Entonces            Escribir Sin Saltar n, " "            contador <- contador + 1        FinSi    FinPara    Escribir ""    Escribir "Encontré ", contador, " números primos."FinAlgoritmo

Flowchart

Each block in the flowchart matches one instruction in the code.

Algoritmo NumerosPrimos
Algoritmo NumerosPrimosSíNoAlgoritmo NumerosPrimosAlgoritmo NumerosPrimosDefinir limite, n, contador Como EnteroDefinir limite, n, contadorComo EnteroEscribir "¿Hasta qué número busco primos?"Escribir "¿Hasta qué númerobusco primos?"Leer limiteLeer limitecontador <- 0contador <- 0Escribir "Primos hasta ", limite, ":"Escribir "Primos hasta ",limite, ":"Para n <- 2 Hasta limite HacerPara n <- 2 Hasta limiteSi EsPrimo(n) EntoncesEsPrimo(n)Escribir Sin Saltar n, " "Escribir Sin Saltar n, " "contador <- contador + 1contador <- contador + 1Escribir ""Escribir ""Escribir "Encontré ", contador, " números primos."Escribir "Encontré ",contador, " números primos."FinAlgoritmoFinAlgoritmo
Funcion EsPrimo
Funcion EsPrimoSíNoSíNoFuncion primo <- EsPrimo(n)Funcion primo <- EsPrimo(n)Definir primo Como LogicoDefinir primo Como LogicoDefinir divisor Como EnteroDefinir divisor Como Enteroprimo <- n > 1primo <- n > 1divisor <- 2divisor <- 2Mientras primo Y divisor * divisor <= n Hacerprimo Y divisor *divisor <= nSi n MOD divisor = 0 Entoncesn MOD divisor = 0primo <- Falsoprimo <- Falsodivisor <- divisor + 1divisor <- divisor + 1FinFuncion (devuelve primo)FinFuncion (devuelve primo)

Sample run

This is what the program shows when it runs. The answers typed by the user are highlighted.

¿Hasta qué número busco primos?User answer: 50Primos hasta 50:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 Encontré 15 números primos.

Complexity

How much work and memory it needs as the amount of data (n) grows.

Complexity
CaseCost
BestO(n√n)
AverageO(n√n)
WorstO(n√n)
MemoryO(1)

Challenge

Also show the sum of all the primes found.

Show hint

Add an accumulator to the Para loop in the main algorithm.

Open in Codoritmo

Related examples