{"id":2426,"date":"2011-08-02T16:32:08","date_gmt":"2011-08-02T14:32:08","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2426"},"modified":"2022-10-11T09:33:33","modified_gmt":"2022-10-11T07:33:33","slug":"il-crivello-dopo-eratostene","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2011\/08\/02\/il-crivello-dopo-eratostene\/","title":{"rendered":"Il crivello dopo Eratostene"},"content":{"rendered":"

Non ho mai capito perch\u00e9 a scuola, almeno quando a scuola ci andavo io, gli insegnanti erano cos\u00ec felici di parlare del crivello di Eratostene, un metodo per trovare tutti i numeri primi inferiori a un limite dato. Secono me la ragione recondita \u00e8 che usare il crivello \u00e8 un esercizio di pazienza degno di un monaco zen. Pur continuando a dover essere pazienti, per\u00f2, si possono trovare crivelli di tipo almeno a prima vista ben diverso!<\/p>\n

Innanzitutto, per chi non sa di che si parli, vi spiego rapidamente cos’\u00e8 il crivello di Eratostene. Anzi, vi dico in due parole chi era Eratostene: un matematico ellenista, pi\u00f9 o meno del periodo tra Euclide e Archimede, che se ne stava ad Alessandria nella Grande Biblioteca ed \u00e8 soprattutto noto per avere stimato con una discreta precisione la circonferenza della Terra – che i greci sapevano perfettamente essere sferica, che credete? <\/p>\n

\"\"<\/a><\/p>\n

Come ho accennato prima, il suo crivello \u00e8 un algoritmo – anche se lui non lo chiamava certo cos\u00ec – per ricavare tutti i numeri primi inferiori a un numero dato. Le istruzioni operative sono semplici, e raffigurate nella figura qui sopra. Innanzitutto si scrivono tutti i numeri da 2 al limite massimo che interessa: vi ricordo che per i greci 1 non era un numero ma il generatore dei numeri, e quindi non si facevano tanti pipponi se 1 fosse o no un numero primo. Poi si prende il primo numero, 2, e si cancellano tutti i suoi multipli: nella figura li ho colorati di verde. Si passa al primo numero rimasto, 3, e si colorano i suoi<\/i> multipli: in questo caso ho usato il giallo. Naturalmente ci saranno numeri che verranno colorati due volte: non importa. Proseguendo, il primo numero rimasto \u00e8 il 5 (azzurro), seguito dal 7 (rosso); dopo aver tolto i mulltipli di quei numeri mi sono fermato perch\u00e9 ero interessato ai numeri fino a 100 e il quadrato del numero seguente, 11, \u00e8 maggiore di 100; anzi avrei potuto aggiungere altri 20 numeri. A questo punto, i numeri rimasti sono tutti e soli i primi nell’insieme di partenza.<\/p>\n

\u00c8 chiaro come mai l’algoritmo funziona: tutti i numeri che si tolgono sono composti, e li abbiamo tolti tutti perch\u00e9 per esempio nel nostro caso non possiamo aver dimenticato 11·p<\/i> con p<\/i> minore di 11, perch\u00e9 l’avremmo gi\u00e0 trovato ed eliminato come p<\/i>·11. \u00c8 per\u00f2 vero che il costo computazionale dell’algoritmo \u00e8 piuttosto alto, richiedendo un numero di operazioni dell’ordine del massimo numero che si vuole verificare, cio\u00e8 O(N) operazioni, e un costo di memoria pari a O(N1\/2<\/sup>(log log N)\/log N) bit di memoria. Non \u00e8 per\u00f2 che in pi\u00f9 di duemila anni si sia cos\u00ec migliorata la ricerca. Eulero si \u00e8 limitato a fare una modifica all’algoritmo (la trovate su Wikipedia in inglese<\/a>) per evitare di cancellare pi\u00f9 volte lo stesso numero; i migliori algoritmi attuali, come il crivello di Atkin<\/a>, hanno costo computazionale pari a O(N\/log log N) operazioni e N1\/2 + o(1)<\/sup> bit di memoria. Paradossalmente cos\u00ec per verificare se un numero \u00e8 primo si preferisce usare un test probabilistico di primalit\u00e0 che non d\u00e0 la certezza assoluta ma quasi; un matematico puro storce immediatamente il naso, ma i numeri primi grandi non servono a loro bens\u00ec agli informatici per generare le chiavi crittografiche e in questo caso una probabilit\u00e0 di non primalit\u00e0 intorno a una parte su 1030<\/sup> non d\u00e0 soverchi problemi.<\/p>\n

Quello che per\u00f2 sono in pochi a sapere \u00e8 che si pu\u00f2 usare un crivello geometrico<\/b> per generare i numeri primi! Il metodo \u00e8 stato esposto da due matematici russi, Yuri Matiyasevich e Boris Stechkin, e prevede l’uso di una parabola, come si pu\u00f2 vedere nella figura qui sotto, tratta dal loro articolo di presentazione<\/a>: per comodit\u00e0 la parabola \u00e8 stata disegnata in orizzontale anzich\u00e9 in verticale, e quindi la sua equazione non \u00e8 la classica y<\/i>=x<\/i>2<\/sup> ma x<\/i>=y<\/i>2<\/sup>. Sull’asse delle x<\/i> si indichino tutti i numeri naturali; sulla parabola si segnino invece quelli che hanno un valore intero per y<\/i> il cui valore assoluto sia maggiore o uguale a 2. L’operazione che si deve ora fare consiste nel disegnare tutti i segmenti che uniscono tra di loro due punti segnati sulla parabola, uno nel semipiano positivo e uno negativo. Questi segmenti toccheranno l’asse delle x<\/i> in un punto; tutti i punti a coordinata intera che non vengono toccati da nessun segmento corrispondono ai numeri primi.<\/p>\n

\"\"<\/a>
\nCome funziona tutto ci\u00f2? Beh, la cosa \u00e8 relativamente semplice. Se un numero n<\/i> \u00e8 esprimibile come prodotto a<\/i>b<\/i> e prendiamo i punti etichettati a<\/i> e b<\/i> sui due rami della parabola, le loro coordinate cartesiane sono (a<\/i>2<\/sup>,a<\/i>) e (b<\/i>2<\/sup>,−b<\/i>). \u00c8 facile vedere che l’intersezione della retta che passa per quei due punti con l’asse delle x<\/i> sar\u00e0 il punto (ab<\/i>,0), dal che si ottiene immediatamente la tesi del teorema (e si capisce perch\u00e9 non si devono usare i due punti di ordinata 1 e −1…) L’utilit\u00e0 pratica di questo crivello \u00e8 pressoch\u00e9 nulla, per\u00f2 dal punto di vista didattico la figura \u00e8 molto interessante, perch\u00e9 permette di visualizzare la fattorizzazione in modo diverso dal solito, e cos\u00ec aiutare la comprensione matematica… voi che ne pensate?<\/p>\n","protected":false},"excerpt":{"rendered":"

Non \u00e8 che ci siano chiss\u00e0 quali metodi per calcolare i numeri primi. Pu\u00f2 essere divertente scoprire che esiste un crivello… geometrico.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2426","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-D8","jetpack-related-posts":[{"id":580,"url":"https:\/\/xmau.com\/ilpost\/2015\/06\/19\/maturita-2015-luci-e-ombre\/","url_meta":{"origin":2426,"position":0},"title":"Maturit\u00e0 2015, luci e ombre","author":".mau.","date":"19\/06\/2015","format":false,"excerpt":"Ottima l'idea di avere un esempio pratico, meno buona quella di un quesito \"facile\" troppo generico","rel":"","context":"In \"dematematizzazione\"","block_context":{"text":"dematematizzazione","link":"https:\/\/xmau.com\/ilpost\/tag\/dematematizzazione\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":672,"url":"https:\/\/xmau.com\/ilpost\/2015\/12\/03\/teoremi-e-probabilita\/","url_meta":{"origin":2426,"position":1},"title":"Teoremi e probabilit\u00e0","author":".mau.","date":"03\/12\/2015","format":false,"excerpt":"Sembrano due concetti agli antipodi, eppure si possono dimostrare alcuni teoremi con metodi probabilistici.","rel":"","context":"In \"dimostrazioni\"","block_context":{"text":"dimostrazioni","link":"https:\/\/xmau.com\/ilpost\/tag\/dimostrazioni\/"},"img":{"alt_text":"cerchi","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2015\/12\/cerchi-300x182.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2470,"url":"https:\/\/xmau.com\/ilpost\/2012\/01\/09\/sudoku-minimali-e-massimali\/","url_meta":{"origin":2426,"position":2},"title":"Sudoku minimali e massimali","author":".mau.","date":"09\/01\/2012","format":false,"excerpt":"Il 2012 si \u00e8 aperto con la dimostrazione che per avere un sudoku risolvibile \u00e8 necessario avere almeno 17 numeri. Come ci si \u00e8 arrivati? Forza (quasi) bruta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2012\/01\/sudoku77.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2632,"url":"https:\/\/xmau.com\/ilpost\/2013\/09\/03\/a-game-of-numbers-pillole\/","url_meta":{"origin":2426,"position":3},"title":"“A game of Numbers” [Pillole]","author":".mau.","date":"03\/09\/2013","format":false,"excerpt":"Iniziamo il cosiddetto \"anno logico\" in maniera leggera.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2596,"url":"https:\/\/xmau.com\/ilpost\/2013\/04\/24\/il-paradosso-delle-due-monete-pillole\/","url_meta":{"origin":2426,"position":4},"title":"Il paradosso delle due monete [Pillole]","author":".mau.","date":"24\/04\/2013","format":false,"excerpt":"Se lanciate una moneta fino a che non esce testa, potete essere molto sfortunati e morire prima di farcela (oppure trovare qualcuno che vi confischi la moneta); ma il numero medio di lanci che vi tocca fare \u00e8 2; questo infatti \u00e8 il valore della somma (1\u00b71\/2 + 2\u00b71\/4 +\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":571,"url":"https:\/\/xmau.com\/ilpost\/2011\/05\/25\/i-numeri-di-munchhausen\/","url_meta":{"origin":2426,"position":5},"title":"I numeri di M\u00fcnchhausen","author":".mau.","date":"25\/05\/2011","format":false,"excerpt":"Come il barone di M\u00fcnchhausen le spara grosse per far credere di essere chiss\u00e0 che cosa, i numeri di M\u00fcnchhausen hanno una definizione pomposa ma poi si scopre che in pratica non esistono.","rel":"","context":"In \"numeri\"","block_context":{"text":"numeri","link":"https:\/\/xmau.com\/ilpost\/tag\/numeri\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2426","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2426"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2426\/revisions"}],"predecessor-version":[{"id":2427,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2426\/revisions\/2427"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2426"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2426"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2426"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}