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: #. Mantenir una llista del tots els naturals del 2 fins un màxim :math:`M`. #. Comencem pel primer més petit de la llista :math:`p=2`. #. Generem els múltiples de :math:`p` (:math:`2p`, :math:`3p`, :math:`\ldots`) fins el màxim :math:`M` i els eliminem de la llista. #. 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 :math:`p` a fer el pas anterior. Si no el trobem ja hem acabat. #. Podem fer algunes simplificacions: #. L'únic primer parell és el 2. La resta són senars. Per tant podríem generar només una llista de senars. .. També se sap que a partir del 3 tots els primers poden representar-se com :math:`6k + 1` o :math:`6k + 5` (o :math:`6k -1`) per :math:`k=1\ldots`. #. Els múltiples a eliminar son a partir de :math:`p\times p`, doncs els d'abans ja han estat eliminats per primers inferiors a :math:`p`. Es disposa ---------- Es disposa del programa :file:`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: .. * La seqüència conté l'enter -1 que separa la seqüència en dues subseqüències de nombres naturals. .. * Anomenem la subseqüència de naturals abans del -1, `esquerra`, i `dreta` la subseqüència que segueix al -1. .. * Els naturals i el nombre separador estan separats sempre per espais o finals de línies. .. * El programa `tria` farà que: * tots els nombres de la subseqüència `esquerra` passin al canal estàndard de sortida * En la subseqúència `dreta`: * El primer (anomenem-lo :math:`p`) de la subseqüència el passarà al canal estàndard de sortida i a continuació passsarà el separador -1 al canal. * Filtrarà tots els nombres múltiples de :math:`p` que vinguin a continuació. Per tant, passaran al canal estàndard de sortida els nombres que no són múltiples de :math:`p`. .. Més formalment, .. automodule:: tria :members: .. L'efecte del programa `tria` està en que si a l'entrada es té una seqüència formada per una subseqüència esquerra de la successió de nombres primers començant pel 2 i la part dreta la successió de naturals senars més gran que el darrer terme o màxim de la part esquerra i que no són múltiples de cap terme de la part esquerra. creixent començant pel, al canal estàndard de sortida apareixerà la part esquerra augmentada amb un nou primer i la part dreta sense cap múltiple del nou primer. 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 :math:`n`. Se sap que només amb :math:`\lfloor\sqrt{n}\rfloor + 1` programes `tria` encadenats es pot per tenir la seqüència de primers compresos entre 3 i :math:`n`. Podeu descarregar-vos el programa :download:`tria.py` i :download:`tria`. Cal que canvieu els atributs de :file:`tria` per a que sigui executable. Es demana --------- #. A l'entrada del pipe podem posar un programa, `compta`, que a partir del paràmetre o argument de la comanda que l'invoca (:code:`compta arg`), :math:`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, .. code-block:: bash $ compta 7 2 -1 3 5 7 Dissenyeu la funció :func:`compta.compta` en el fitxer :file:`compta.py`: .. automodule:: compta :members: Dissenyeu també el fitxer executable :file:`compta` que invoca python3 pel sistema, importa el fitxer :file:`compta.py` i crida la funció anterior passant-li l'argument trobat a la línia. #. Com que encadenant :math:`\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 :math:`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 :file:`final` que importa la funció :func:`final.final` del fitxer :file:`final.py`. Dissenyeu la funció :func:`final.final` en el fitxer :file:`final.py`: .. automodule:: final :members: Es recomana usar l'objecte :code:`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 #. Finalment, dissenyeu un guió en bash en el fitxer :file:`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 #. Es demana el mateix que l'apartat anterior però fent-ho des d'un programa de python usant la funció :code:`Popen` de la biblioteca :code:`subprocess`. En comptes de 32 per un nombre qualsevol present com argument de la línia que crida el programa. Si :math:`n` és el nombre donat, el nombre de filtres necesaris per tenir a la sortida tots els nombres primers menors que :math:`n` és :math:`\lfloor \sqrt{n} \rfloor + 1`