Generació successió nombres primers

Context

El sedàs o garbell d’Eratòstenes (veure article) és un mètode ràpid per generar nombres primers des de 2 fins un nombre màxim.

El mètode de generació consisteix en:

  1. Mantenir una llista del tots els naturals del 2 fins un màxim \(M\).

  2. Comencem pel primer més petit de la llista \(p=2\).

  3. Generem els múltiples de \(p\) (\(2p\), \(3p\), \(\ldots\)) fins el màxim \(M\) i els eliminem de la llista.

  4. Cerquem el nombre més gran que p i més petit de la llista que no ha estat eliminat. Si el trobem tenim el següent primer \(p\) a fer el pas anterior. Si no el trobem ja hem acabat.

  5. Podem fer algunes simplificacions:

    1. L’únic primer parell és el 2. La resta són senars. Per tant podríem generar només una llista de senars.

    1. Els múltiples a eliminar son a partir de \(p\times p\), doncs els d’abans ja han estat eliminats per primers inferiors a \(p\).

Es disposa

Es disposa del programa tria que rep pel canal estàndard d’entrada una seqüència textual d’enters que està estructurada i definida de la següent forma:

tria.tria()

Rep pel canal estàndard d’entrada la seqüència textual de línies que contenen un nombre. La seqüència de nombres la podem caracteritzar com:

\(p_1\ p_2 \ldots p_e\ -1\ n_1\ n_2\ \ldots n_d\)

on hi ha un únic nombre -1 que separa la seqüència en dos subseqüències de naturals: esquerra i dreta.

L”esquerra conté els \(e\) primers primers a partir del 2 (\(p_1=2\)) i \(p_i<p_{i+1}\quad \forall i:1\le i < e\).

La dreta son tots els naturals creixents fins \(n_d\) i no múltiples de cap \(p_i\quad \forall i:1\le i \le e\) i \(n_i<n_{i+1}\quad \forall i:1\le i < d\) i \(n_1 > p_e\).

Pel canal estandard de sortida, obtindrem

\(p_1\ p_2 \ldots p_{e + 1}\ -1\ m_1\ m_2\ \ldots m_r\)

on

\(p_i> 0\quad 1\le i \le e\) i \(p_i\) son els \(e+1\) primers primers a partir del 2 (\(p_1= 2\)). És a dir, té un primer més que la subseqüència esquerra d’entrada; i

la nova part dreta segueix complint les mateixes propietats que la de l’entrada amb probablement menys nombres: cap múltiple de \(p_i\quad \forall i:1\le i \le e\) i \(m_i<m_{i+1}\quad \forall i:1\le i < d\) i \(m_1 > p_{e+1}\). La nova part pot ser buïda si a l’entrada només havia un nombre: \(r\le d\).

Per exemple,:

$ echo -e  "2\n3\n-1\n5\n7\n11\n13\n15" | tria
2
3
5
-1
7
11
13

Encadenant diversos programes tria com a pipe podem determinar els nombres primers d’una seqüència de nombres naturals senars de 3 fins a \(n\). Se sap que només amb \(\lfloor\sqrt{n}\rfloor + 1\) programes tria encadenats es pot per tenir la seqüència de primers compresos entre 3 i \(n\).

Podeu descarregar-vos el programa tria.py i tria. Cal que canvieu els atributs de tria per a que sigui executable.

Es demana

  1. A l’entrada del pipe podem posar un programa, compta, que a partir del paràmetre o argument de la comanda que l’invoca (compta arg), \(arg\) escriu al canal estàndard de sortida una seqüència textual d’enters que comença per 2 -1 i continua com una seqüència de senars que progressivament van de 3 fins arg.

    Per exemple,

    $ compta 7
2
-1
3
5
7

    Dissenyeu la funció compta.compta() en el fitxer compta.py:

    compta.compta(n)

    Genera i escriu al canal estàndard de sortida una seqüencia textual de nombres: \(2\ -1\ e_1\ e_2\ \ldots\ e_n\) on \(e_n\le n\), \(e_j=2j +1\), i \(\forall j:\quad 1\le j\le \lfloor{n + 1\over 2}\rfloor - 1\).

    Parameters:

    n – Límit del valor del darrer senar de la seqüència.

    Returns:

    None

    Dissenyeu també el fitxer executable compta que invoca python3 pel sistema, importa el fitxer compta.py i crida la funció anterior passant-li l’argument trobat a la línia.

  2. Com que encadenant \(\lfloor\sqrt{n}\rfloor + 1\) programes tria com a pipe podem determinar els nombres primers d’una seqüència de nombres naturals senars de 3 fins a \(n\), el resultat en el canal estàndard de sortida de la darrera etapa pot contenir el separador -1 entre la seqüència ja definitiva de primers. Es tracta aquí de dissenyar un programa anomenat final (fitxer text final que importa la funció final.final() del fitxer final.py.

    Dissenyeu la funció final.final() en el fitxer final.py:

    final.final()

    Pel canal estàndard d’entrada ens arriba un text en que cada línia hi ha un nombre enter. Cadascun d’aquests enters s’escriu al canal estàndard de sortida excepte si l’enter en qüestió és -1. És a dir filtra els valors -1.

    Cap paràmetre ni retorn.

    Es recomana usar l’objecte sys.stdin de la biblioteca sys que es comporta igual que un fitxer de python i gestiona el canal estàndard d’entrada.

    Exemple d’ús:

    $ echo -e "2\n-1\n3\n5\n7" | final
2
3
5
7

  3. Finalment, dissenyeu un guió en bash en el fitxer primers32.sh que encadeni en forma de pipe els programes compta, tria, i final i tregui pel canal estàndard de sortida els nombres primers menors que 32.

    Un exemple d’us:

    $ bash primers32.sh
2
3
5
7
11
13
17
19
23
29
31

  4. Es demana el mateix que l’apartat anterior però fent-ho des d’un programa de python usant la funció Popen de la biblioteca subprocess. En comptes de 32 per un nombre qualsevol present com argument de la línia que crida el programa. Si \(n\) és el nombre donat, el nombre de filtres necesaris per tenir a la sortida tots els nombres primers menors que \(n\) és \(\lfloor \sqrt{n} \rfloor + 1\)