Garbell d'Eratòstenes P75445

El garbell d’Eratòstenes és un algorisme que troba tots els nombres primers fins a un cert nombre $N$. El procediment és el següent:

1. Es crea una llista $L$ amb tots els nombres des de $2$ fins a $N$.

2. Per a cada $j$ des de 2 fins a $\lfloor\sqrt{N}\rfloor$, si $j$ encara es troba a $L$, esborrem d’$L$ tots els múltiples de $j$ més grans que $j$.

En acabar, només romandran a $L$ els nombres primers.

Per exemple, amb $N=18$, inicialment $L = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]$. Després de l’iteració amb $j=2$, tenim $L = [2, 3, 5, 7, 9, 11, 13, 15, 17]$. Després de l’iteració amb $j=3$, tenim $L = [2, 3, 5, 7, 11, 13, 17]$. L’iteració amb $j=4$ no canvia $L$ perquè 4 no hi és. Ara l’algorisme s’atura perquè $5 \cdot 5 = 25 > N$.

Donats tres enters $n, m, k$ i dos colors $p$ i $c$, heu de simular el garbell d’Eratòstenes per a $N = n \cdot m$, parant l’algorisme després de la iteració amb $j = k$. Heu de pintar els nombres supervivents després de la iteració amb $j=k$ (que són primers si $j$ és prou gran) amb el color $p$, i els altres amb el color $c$.

Entrada

L’entrada té cinc línies. Les tres primeres contenen els enters positius $n$, $m$ i $k$, i les dues següents els colors $p$ i $c$. Assumiu $N \ge 2$ i $2 \le k \le \sqrt{N}$.

Sortida

Dibuixeu una graella amb $n$ files i $m$ columnes, on cada casella té $10 \times 10$ píxels. Suposeu que disposem els nombres des d’1 fins a $N$ sobre aquesta graella, de manera que la primera fila té els nombres $1, \dots, m$, la segona fila els nombres $m+1, \dots, 2m$, etc. Les caselles corresponents a nombres que encara es troben a $L$ al final de l’algorisme s’han de pintar de color $p$, i les altres (inclosa la casella 1) de color $c$.