Garbell d'Eratòstenes P75445

Graphic problem

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 ⌊√N⌋, 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 · 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 · 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 ≥ 2 i 2 ≤ k ≤ √N.

Sortida

Dibuixeu una graella amb n files i m columnes, on cada casella té 10 × 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, …, m, la segona fila els nombres m+1, …, 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.