CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="it" dir="ltr"> <head> <meta charset="UTF-8"> <title>Crivello di Atkin - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )itwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""], "wgDefaultDateFormat":"dmy","wgMonthNames":["","gennaio","febbraio","marzo","aprile","maggio","giugno","luglio","agosto","settembre","ottobre","novembre","dicembre"],"wgRequestId":"28899703-eeda-4eb8-8350-a78cfcbacd3a","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Crivello_di_Atkin","wgTitle":"Crivello di Atkin","wgCurRevisionId":135600914,"wgRevisionId":135600914,"wgArticleId":626694,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Informazioni senza fonte","Algoritmi per la matematica","Numeri primi"],"wgPageViewLanguage":"it","wgPageContentLanguage":"it","wgPageContentModel":"wikitext","wgRelevantPageName":"Crivello_di_Atkin","wgRelevantArticleId":626694,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgMediaViewerOnClick":true, "wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"it","pageLanguageDir":"ltr","pageVariantFallbacks":"it"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":10000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1542201","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready" ,"user.options":"loading","ext.cite.styles":"ready","ext.pygments":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.MainPageWikiList","ext.gadget.stru-commonsupload","ext.gadget.HiddenCat","ext.gadget.ReferenceTooltips","ext.gadget.TitoloErrato","ext.gadget.NewSection","ext.gadget.RichiediRevisioneBozza","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init", "ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=it&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=it&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=it&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.6"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Crivello di Atkin - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//it.m.wikipedia.org/wiki/Crivello_di_Atkin"> <link rel="alternate" type="application/x-wiki" title="Modifica" href="/w/index.php?title=Crivello_di_Atkin&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (it)"> <link rel="EditURI" type="application/rsd+xml" href="//it.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://it.wikipedia.org/wiki/Crivello_di_Atkin"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.it"> <link rel="alternate" type="application/atom+xml" title="Feed Atom di Wikipedia" href="/w/index.php?title=Speciale:UltimeModifiche&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Crivello_di_Atkin rootpage-Crivello_di_Atkin skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Vai al contenuto</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Sito"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Menu principale" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Menu principale</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Menu principale</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">nascondi</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigazione </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Pagina_principale" title="Visita la pagina principale [z]" accesskey="z"><span>Pagina principale</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Speciale:UltimeModifiche" title="Elenco delle ultime modifiche del sito [r]" accesskey="r"><span>Ultime modifiche</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Speciale:PaginaCasuale" title="Mostra una pagina a caso [x]" accesskey="x"><span>Una voce a caso</span></a></li><li id="n-nearby-pages-title" class="mw-list-item"><a href="/wiki/Speciale:NelleVicinanze"><span>Nelle vicinanze</span></a></li><li id="n-vetrina" class="mw-list-item"><a href="/wiki/Wikipedia:Vetrina"><span>Vetrina</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Aiuto:Aiuto" title="Pagine di aiuto"><span>Aiuto</span></a></li><li id="n-Sportello-informazioni" class="mw-list-item"><a href="/wiki/Aiuto:Sportello_informazioni"><span>Sportello informazioni</span></a></li> </ul> </div> </div> <div id="p-Comunità" class="vector-menu mw-portlet mw-portlet-Comunità" > <div class="vector-menu-heading"> Comunità </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-portal" class="mw-list-item"><a href="/wiki/Portale:Comunit%C3%A0" title="Descrizione del progetto, cosa puoi fare, dove trovare le cose"><span>Portale Comunità</span></a></li><li id="n-villagepump" class="mw-list-item"><a href="/wiki/Wikipedia:Bar"><span>Bar</span></a></li><li id="n-wikipediano" class="mw-list-item"><a href="/wiki/Wikipedia:Wikipediano"><span>Il Wikipediano</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="/wiki/Wikipedia:Contatti"><span>Contatti</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Pagina_principale" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="L'enciclopedia libera" src="/static/images/mobile/copyright/wikipedia-tagline-it.svg" width="120" height="13" style="width: 7.5em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Speciale:Ricerca" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Cerca in Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Ricerca</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Cerca in Wikipedia" aria-label="Cerca in Wikipedia" autocapitalize="sentences" title="Cerca in Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Speciale:Ricerca"> </div> <button class="cdx-button cdx-search-input__end-button">Ricerca</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Strumenti personali"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Aspetto"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Modifica la dimensione, la larghezza e il colore del testo" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Aspetto" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Aspetto</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=it.wikipedia.org&uselang=it" class=""><span>Fai una donazione</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Speciale:CreaUtenza&returnto=Crivello+di+Atkin" title="Si consiglia di registrarsi e di effettuare l'accesso, anche se non è obbligatorio" class=""><span>registrati</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Speciale:Entra&returnto=Crivello+di+Atkin" title="Si consiglia di effettuare l'accesso, anche se non è obbligatorio [o]" accesskey="o" class=""><span>entra</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Altre opzioni" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Strumenti personali" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Strumenti personali</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menu utente" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=it.wikipedia.org&uselang=it"><span>Fai una donazione</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Speciale:CreaUtenza&returnto=Crivello+di+Atkin" title="Si consiglia di registrarsi e di effettuare l'accesso, anche se non è obbligatorio"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>registrati</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Speciale:Entra&returnto=Crivello+di+Atkin" title="Si consiglia di effettuare l'accesso, anche se non è obbligatorio [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>entra</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pagine per utenti anonimi <a href="/wiki/Aiuto:Benvenuto" aria-label="Ulteriori informazioni sulla contribuzione"><span>ulteriori informazioni</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Speciale:MieiContributi" title="Un elenco delle modifiche fatte da questo indirizzo IP [y]" accesskey="y"><span>contributi</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Speciale:MieDiscussioni" title="Discussioni sulle modifiche fatte da questo indirizzo IP [n]" accesskey="n"><span>discussioni</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Sito"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Indice" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Indice</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">nascondi</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">Inizio</div> </a> </li> <li id="toc-Algoritmo" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Algoritmo"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Algoritmo</span> </div> </a> <ul id="toc-Algoritmo-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Pseudocodice" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Pseudocodice"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Pseudocodice</span> </div> </a> <ul id="toc-Pseudocodice-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Spiegazione" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Spiegazione"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Spiegazione</span> </div> </a> <ul id="toc-Spiegazione-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Complessità_computazionale" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Complessità_computazionale"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Complessità computazionale</span> </div> </a> <ul id="toc-Complessità_computazionale-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Note" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Note"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Note</span> </div> </a> <ul id="toc-Note-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Voci_correlate" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Voci_correlate"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Voci correlate</span> </div> </a> <ul id="toc-Voci_correlate-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Collegamenti_esterni" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Collegamenti_esterni"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Collegamenti esterni</span> </div> </a> <ul id="toc-Collegamenti_esterni-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Indice" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Mostra/Nascondi l'indice" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Mostra/Nascondi l'indice</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Crivello di Atkin</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Vai a una voce in un'altra lingua. Disponibile in 18 lingue" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-18" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">18 lingue</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%BA%D8%B1%D8%A8%D8%A7%D9%84_%D8%A3%D8%AA%D9%83%D9%8A%D9%86" title="غربال أتكين - arabo" lang="ar" hreflang="ar" data-title="غربال أتكين" data-language-autonym="العربية" data-language-local-name="arabo" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%BD%D0%B0_%D0%90%D1%82%D0%BA%D0%B8%D0%BD" title="Решето на Аткин - bulgaro" lang="bg" hreflang="bg" data-title="Решето на Аткин" data-language-autonym="Български" data-language-local-name="bulgaro" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Sieb_von_Atkin" title="Sieb von Atkin - tedesco" lang="de" hreflang="de" data-title="Sieb von Atkin" data-language-autonym="Deutsch" data-language-local-name="tedesco" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Sieve_of_Atkin" title="Sieve of Atkin - inglese" lang="en" hreflang="en" data-title="Sieve of Atkin" data-language-autonym="English" data-language-local-name="inglese" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Criba_de_Atkin" title="Criba de Atkin - spagnolo" lang="es" hreflang="es" data-title="Criba de Atkin" data-language-autonym="Español" data-language-local-name="spagnolo" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%BA%D8%B1%D8%A8%D8%A7%D9%84_%D8%A7%D8%AA%DA%A9%DB%8C%D9%86" title="غربال اتکین - persiano" lang="fa" hreflang="fa" data-title="غربال اتکین" data-language-autonym="فارسی" data-language-local-name="persiano" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Crible_d%27Atkin" title="Crible d'Atkin - francese" lang="fr" hreflang="fr" data-title="Crible d'Atkin" data-language-autonym="Français" data-language-local-name="francese" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%94%D7%A0%D7%A4%D7%94_%D7%A9%D7%9C_%D7%90%D7%98%D7%A7%D7%99%D7%9F" title="הנפה של אטקין - ebraico" lang="he" hreflang="he" data-title="הנפה של אטקין" data-language-autonym="עברית" data-language-local-name="ebraico" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Tapis_Atkin" title="Tapis Atkin - indonesiano" lang="id" hreflang="id" data-title="Tapis Atkin" data-language-autonym="Bahasa Indonesia" data-language-local-name="indonesiano" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%88%E3%82%AD%E3%83%B3%E3%81%AE%E7%AF%A9" title="アトキンの篩 - giapponese" lang="ja" hreflang="ja" data-title="アトキンの篩" data-language-autonym="日本語" data-language-local-name="giapponese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-ms mw-list-item"><a href="https://ms.wikipedia.org/wiki/Saringan_Atkin" title="Saringan Atkin - malese" lang="ms" hreflang="ms" data-title="Saringan Atkin" data-language-autonym="Bahasa Melayu" data-language-local-name="malese" class="interlanguage-link-target"><span>Bahasa Melayu</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Sito_Atkina" title="Sito Atkina - polacco" lang="pl" hreflang="pl" data-title="Sito Atkina" data-language-autonym="Polski" data-language-local-name="polacco" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Crivo_de_Atkin" title="Crivo de Atkin - portoghese" lang="pt" hreflang="pt" data-title="Crivo de Atkin" data-language-autonym="Português" data-language-local-name="portoghese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Ciurul_lui_Atkin" title="Ciurul lui Atkin - rumeno" lang="ro" hreflang="ro" data-title="Ciurul lui Atkin" data-language-autonym="Română" data-language-local-name="rumeno" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%90%D1%82%D0%BA%D0%B8%D0%BD%D0%B0" title="Решето Аткина - russo" lang="ru" hreflang="ru" data-title="Решето Аткина" data-language-autonym="Русский" data-language-local-name="russo" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%90%D1%82%D0%BA%D0%B8%D0%BD%D0%BE%D0%B2%D0%BE_%D1%81%D0%B8%D1%82%D0%BE" title="Аткиново сито - serbo" lang="sr" hreflang="sr" data-title="Аткиново сито" data-language-autonym="Српски / srpski" data-language-local-name="serbo" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%90%D1%82%D0%BA%D1%96%D0%BD%D0%B0" title="Решето Аткіна - ucraino" lang="uk" hreflang="uk" data-title="Решето Аткіна" data-language-autonym="Українська" data-language-local-name="ucraino" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/S%C3%A0ng_Atkin" title="Sàng Atkin - vietnamita" lang="vi" hreflang="vi" data-title="Sàng Atkin" data-language-autonym="Tiếng Việt" data-language-local-name="vietnamita" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1542201#sitelinks-wikipedia" title="Modifica collegamenti interlinguistici" class="wbc-editpage">Modifica collegamenti</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespace"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Crivello_di_Atkin" title="Vedi la voce [c]" accesskey="c"><span>Voce</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Discussione:Crivello_di_Atkin" rel="discussion" title="Vedi le discussioni relative a questa pagina [t]" accesskey="t"><span>Discussione</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Cambia versione linguistica" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">italiano</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Visite"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Crivello_di_Atkin"><span>Leggi</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Crivello_di_Atkin&veaction=edit" title="Modifica questa pagina [v]" accesskey="v"><span>Modifica</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Crivello_di_Atkin&action=edit" title="Modifica il wikitesto di questa pagina [e]" accesskey="e"><span>Modifica wikitesto</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Crivello_di_Atkin&action=history" title="Versioni precedenti di questa pagina [h]" accesskey="h"><span>Cronologia</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Strumenti pagine"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Strumenti" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Strumenti</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Strumenti</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">nascondi</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Altre opzioni" > <div class="vector-menu-heading"> Azioni </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Crivello_di_Atkin"><span>Leggi</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Crivello_di_Atkin&veaction=edit" title="Modifica questa pagina [v]" accesskey="v"><span>Modifica</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Crivello_di_Atkin&action=edit" title="Modifica il wikitesto di questa pagina [e]" accesskey="e"><span>Modifica wikitesto</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Crivello_di_Atkin&action=history"><span>Cronologia</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Generale </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Speciale:PuntanoQui/Crivello_di_Atkin" title="Elenco di tutte le pagine che sono collegate a questa [j]" accesskey="j"><span>Puntano qui</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Speciale:ModificheCorrelate/Crivello_di_Atkin" rel="nofollow" title="Elenco delle ultime modifiche alle pagine collegate a questa [k]" accesskey="k"><span>Modifiche correlate</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Speciale:PagineSpeciali" title="Elenco di tutte le pagine speciali [q]" accesskey="q"><span>Pagine speciali</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Crivello_di_Atkin&oldid=135600914" title="Collegamento permanente a questa versione di questa pagina"><span>Link permanente</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Crivello_di_Atkin&action=info" title="Ulteriori informazioni su questa pagina"><span>Informazioni pagina</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Speciale:Cita&page=Crivello_di_Atkin&id=135600914&wpFormIdentifier=titleform" title="Informazioni su come citare questa pagina"><span>Cita questa voce</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Speciale:UrlQ%C4%B1sald%C4%B1c%C4%B1s%C4%B1&url=https%3A%2F%2Fit.wikipedia.org%2Fwiki%2FCrivello_di_Atkin"><span>Ottieni URL breve</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Speciale:QrKodu&url=https%3A%2F%2Fit.wikipedia.org%2Fwiki%2FCrivello_di_Atkin"><span>Scarica codice QR</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Stampa/esporta </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=Speciale:Libro&bookcmd=book_creator&referer=Crivello+di+Atkin"><span>Crea un libro</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Speciale:DownloadAsPdf&page=Crivello_di_Atkin&action=show-download-screen"><span>Scarica come PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Crivello_di_Atkin&printable=yes" title="Versione stampabile di questa pagina [p]" accesskey="p"><span>Versione stampabile</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In altri progetti </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1542201" title="Collegamento all'elemento connesso dell'archivio dati [g]" accesskey="g"><span>Elemento Wikidata</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Strumenti pagine"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Aspetto"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Aspetto</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">nascondi</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">Da Wikipedia, l'enciclopedia libera.</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="it" dir="ltr"><p>Il <b>crivello di Atkin</b> è un <a href="/wiki/Algoritmo" title="Algoritmo">algoritmo</a> <a href="/wiki/Matematica" title="Matematica">matematico</a> veloce e moderno per trovare tutti i <a href="/wiki/Numeri_primi" class="mw-redirect" title="Numeri primi">numeri primi</a> fino a uno specifico valore intero. È una versione ottimizzata dell'antico <a href="/wiki/Crivello_di_Eratostene" title="Crivello di Eratostene">crivello di Eratostene</a>: il crivello di Atkin compie del lavoro preliminare, poi segna non tutti i multipli dei primi, ma i multipli dei quadrati dei primi. Fu creato da <a href="/w/index.php?title=A._O._L._Atkin&action=edit&redlink=1" class="new" title="A. O. L. Atkin (la pagina non esiste)">A. O. L. Atkin</a> e <a href="/wiki/Daniel_J._Bernstein" title="Daniel J. Bernstein">Daniel J. Bernstein</a>.<sup id="cite_ref-paper_1-0" class="reference"><a href="#cite_note-paper-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Algoritmo">Algoritmo</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Crivello_di_Atkin&veaction=edit&section=1" title="Modifica la sezione Algoritmo" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Crivello_di_Atkin&action=edit&section=1" title="Edit section's source code: Algoritmo"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Nell'algoritmo: </p> <ul><li>tutti i resti sono <a href="/wiki/Aritmetica_modulare#Le_classi_di_resto_modulo_n" title="Aritmetica modulare">classi di resto in modulo</a> sessanta (si divide il numero per 60 e si guarda il <a href="/wiki/Resto" title="Resto">resto</a>);</li> <li>tutti i numeri, inclusi <i>x</i> e <i>y</i>, sono interi e positivi;</li> <li>alternare un elemento nella lista del crivello, significa cambiare il valore (primo o non_primo) nel valore opposto.</li></ul> <p>I passi sono: </p> <ol><li>creare una lista dei risultati, composta di 2, 3, e 5;</li> <li>creare una lista del crivello con un elemento per ogni <a href="/wiki/Numero_intero" title="Numero intero">numero intero</a> positivo; tutti gli elementi di questa lista devono avere valore non_primo;</li> <li>per ogni elemento nella lista del crivello: <ul><li>se l'elemento è un numero con resto 1, 13, 17, 29, 37, 41, 49, o 53, alternarla un numero di volte uguale alle possibili soluzioni di 4<i>x</i><sup>2</sup> + <i>y</i><sup>2</sup> = <i>numero_dell'elemento</i>;</li> <li>se l'elemento è un numero con resto 7, 19, 31, o 43, alternarla un numero di volte uguale alle possibili soluzioni di 3<i>x</i><sup>2</sup> + <i>y</i><sup>2</sup> = <i>numero_dell'elemento</i>;</li> <li>se l'elemento è un numero con resto 11, 23, 47, o 59, alternarla un numero di volte uguale alle possibili soluzioni di 3<i>x</i><sup>2</sup> - <i>y</i><sup>2</sup> = <i>numero_dell'elemento</i> con <i>x</i> > <i>y</i>;</li> <li>se l'elemento ha qualche altro resto, ignorarlo completamente;</li></ul></li> <li>cominciare con il numero più piccolo della lista del crivello;</li> <li>prendere il prossimo numero con valore primo della lista del crivello;</li> <li>aggiungere questo numero alla lista dei risultati;</li> <li>effettuare il quadrato del numero, e assegnare a tutti i multipli del quadrato il "flag" non_primo;</li> <li>ripetere i passaggi da 5 a 8.</li></ol> <p>Il punto 3 si può anche eseguire al contrario, provando tutti i valori di <i>x</i> e <i>y</i> e alternando l'elemento corrispondente a 4<i>x</i><sup>2</sup> + <i>y</i><sup>2</sup>, 3<i>x</i><sup>2</sup> + <i>y</i><sup>2</sup> e 3<i>x</i><sup>2</sup> -<i>y</i><sup>2</sup> se il risultato ha resto pari a quello indicato nella descrizione qui sopra. </p> <div class="mw-heading mw-heading2"><h2 id="Pseudocodice">Pseudocodice</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Crivello_di_Atkin&veaction=edit&section=2" title="Modifica la sezione Pseudocodice" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Crivello_di_Atkin&action=edit&section=2" title="Edit section's source code: Pseudocodice"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Quanto segue è lo <a href="/wiki/Pseudocodice" title="Pseudocodice">pseudocodice</a> per una versione semplice dell'<a href="/wiki/Algoritmo" title="Algoritmo">algoritmo</a>: </p> <div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre><span></span><span class="n">limit</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1000000</span><span class="p">;</span><span class="w"> </span><span class="c1">// Limite arbitrario di ricerca</span> <span class="n">array</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="mi">5</span><span class="o">:</span><span class="n">limit</span><span class="p">]</span><span class="w"> </span><span class="n">initial</span><span class="w"> </span><span class="nb">false</span><span class="p">;</span><span class="w"> </span><span class="c1">// Array del crivello</span> <span class="n">biginteger</span><span class="w"> </span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">,</span><span class="n">n</span><span class="p">,</span><span class="n">k</span><span class="p">;</span><span class="w"> </span><span class="c1">// Dev'essere capace di contenere 5*limit: 4x^2 + y^2!</span> <span class="c1">// put in candidate primes: integers which have an odd number of representations by certain quadratic forms.</span> <span class="k">for</span><span class="w"> </span><span class="n">x</span><span class="o">:=</span><span class="mi">1</span><span class="o">:</span><span class="n">sqrt</span><span class="p">(</span><span class="n">limit</span><span class="p">)</span><span class="w"> </span><span class="k">do</span> <span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">y</span><span class="o">:=</span><span class="mi">1</span><span class="o">:</span><span class="n">sqrt</span><span class="p">(</span><span class="n">limit</span><span class="p">)</span><span class="w"> </span><span class="k">do</span> <span class="w"> </span><span class="nl">n</span><span class="p">:</span><span class="o">=</span><span class="mi">4</span><span class="n">x</span><span class="o">^</span><span class="mi">2</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">y</span><span class="o">^</span><span class="mi">2</span><span class="p">;</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o"><=</span><span class="w"> </span><span class="n">limit</span><span class="w"> </span><span class="n">and</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="n">mod</span><span class="w"> </span><span class="mi">12</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="n">or</span><span class="w"> </span><span class="mi">5</span><span class="w"> </span><span class="n">then</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="o">:=</span><span class="n">not</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="n">n</span><span class="p">];</span> <span class="w"> </span><span class="nl">n</span><span class="p">:</span><span class="o">=</span><span class="mi">3</span><span class="n">x</span><span class="o">^</span><span class="mi">2</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">y</span><span class="o">^</span><span class="mi">2</span><span class="p">;</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o"><=</span><span class="w"> </span><span class="n">limit</span><span class="w"> </span><span class="n">and</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="n">mod</span><span class="w"> </span><span class="mi">12</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">7</span><span class="w"> </span><span class="n">then</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="o">:=</span><span class="n">not</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="n">n</span><span class="p">];</span> <span class="w"> </span><span class="nl">n</span><span class="p">:</span><span class="o">=</span><span class="mi">3</span><span class="n">x</span><span class="o">^</span><span class="mi">2</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="n">y</span><span class="o">^</span><span class="mi">2</span><span class="p">;</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o"><=</span><span class="w"> </span><span class="n">limit</span><span class="w"> </span><span class="n">and</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="n">and</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="n">mod</span><span class="w"> </span><span class="mi">12</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">11</span><span class="w"> </span><span class="n">then</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="o">:=</span><span class="n">not</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="n">n</span><span class="p">];</span> <span class="w"> </span><span class="n">next</span><span class="w"> </span><span class="n">y</span><span class="p">;</span> <span class="n">next</span><span class="w"> </span><span class="n">x</span><span class="p">;</span> <span class="c1">// Eliminazione dei numeri non primi setacciando i risultati rimanenti</span> <span class="c1">// Se n è primo, elimina tutti i multipli del suo quadrato; i numeri</span> <span class="c1">// composti che sono rimasti nella lista devono avere fattori primi</span> <span class="c1">// con esponente pari.</span> <span class="k">for</span><span class="w"> </span><span class="n">n</span><span class="o">:=</span><span class="mi">5</span><span class="o">:</span><span class="n">sqrt</span><span class="p">(</span><span class="n">limit</span><span class="p">)</span><span class="w"> </span><span class="k">do</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="w"> </span><span class="n">then</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">k</span><span class="o">:=</span><span class="n">n</span><span class="o">^</span><span class="mi">2</span><span class="o">:</span><span class="n">limit</span><span class="o">:</span><span class="n">n</span><span class="o">^</span><span class="mi">2</span><span class="w"> </span><span class="k">do</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">:=</span><span class="nb">false</span><span class="p">;</span><span class="w"> </span><span class="n">next</span><span class="w"> </span><span class="n">k</span><span class="p">;</span> <span class="n">next</span><span class="w"> </span><span class="n">n</span><span class="p">;</span> <span class="c1">// Presentazione dei risultati</span> <span class="n">print</span><span class="w"> </span><span class="mi">2</span><span class="p">,</span><span class="w"> </span><span class="mi">3</span><span class="p">;</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">n</span><span class="o">:=</span><span class="w"> </span><span class="mi">5</span><span class="o">:</span><span class="n">limit</span><span class="w"> </span><span class="k">do</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">is_prime</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="w"> </span><span class="n">then</span><span class="w"> </span><span class="n">print</span><span class="w"> </span><span class="n">n</span><span class="p">;</span><span class="w"> </span><span class="n">next</span><span class="w"> </span><span class="n">n</span><span class="p">;</span> </pre></div> <p>Notare che questo pseudocodice è più lento rispetto al crivello di Eratostene. Per migliorare la sua efficienza, bisogna usare un metodo più veloce per la soluzione delle tre equazioni quadratiche. È possibile utilizzare a tale scopo l'identità <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x+1)^{2}=x^{2}+2x+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>x</mi> <mo>+</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>=</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>2</mn> <mi>x</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x+1)^{2}=x^{2}+2x+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c74cf24f6c2c6a8d218b4311d2c56e885ac59a29" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.014ex; height:3.176ex;" alt="{\displaystyle (x+1)^{2}=x^{2}+2x+1}"></span> per non calcolare i quadrati di <i>x</i> e <i>y</i>, e calcolare il modulo delle tre funzioni quadratiche a partire dal modulo di <i>x</i> e <i>y</i> come nelle seguenti tabelle<style data-mw-deduplicate="TemplateStyles:r140554517">.mw-parser-output .chiarimento{background:#ffeaea;color:#444444}.mw-parser-output .chiarimento-apice{color:#EE0700}@media screen{html.skin-theme-clientpref-night .mw-parser-output .chiarimento{background:rgba(179,36,36,0.21);color:inherit}html.skin-theme-clientpref-night .mw-parser-output .chiarimento-apice{color:#b32424}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .chiarimento{background:rgba(179,36,36,0.21);color:inherit}html.skin-theme-clientpref-os .mw-parser-output .chiarimento-apice{color:#b32424}}</style><span class="chiarimento" title="Queste informazioni non sono comprovate da fonti attendibili."></span><sup class="noprint chiarimento-apice" title="Queste informazioni non sono comprovate da fonti attendibili.">[<i><a href="/wiki/Wikipedia:Uso_delle_fonti" title="Wikipedia:Uso delle fonti">senza fonte</a></i>]</sup>: </p> <div style="float:left; width: 50%; text-align: center; margin: 0 auto"> <p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4x^{2}+y^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>4</mn> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 4x^{2}+y^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1461da7f341fca0a5ab85c22253aa69ef6694dc7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.601ex; height:3.009ex;" alt="{\displaystyle 4x^{2}+y^{2}}"></span> </p> <table class="wikitable" style="margin:auto;clear:both;"> <tbody><tr> <th>y\x </th> <th>0</th> <th>1</th> <th>2</th> <th>3</th> <th>4</th> <th>5</th> <th>6</th> <th>7</th> <th>8</th> <th>9</th> <th>10</th> <th>11 </th></tr> <tr> <th>0 </th> <td>0</td> <td>4</td> <td>4</td> <td>0</td> <td>4</td> <td>4</td> <td>0</td> <td>4</td> <td>4</td> <td>0</td> <td>4</td> <td>4 </td></tr> <tr> <th>1 </th> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5 </td></tr> <tr> <th>2 </th> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8 </td></tr> <tr> <th>3 </th> <td>9</td> <td>1</td> <td>1</td> <td>9</td> <td>1</td> <td>1</td> <td>9</td> <td>1</td> <td>1</td> <td>9</td> <td>1</td> <td>1 </td></tr> <tr> <th>4 </th> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8 </td></tr> <tr> <th>5 </th> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5 </td></tr> <tr> <th>6 </th> <td>0</td> <td>4</td> <td>4</td> <td>0</td> <td>4</td> <td>4</td> <td>0</td> <td>4</td> <td>4</td> <td>0</td> <td>4</td> <td>4 </td></tr> <tr> <th>7 </th> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5 </td></tr> <tr> <th>8 </th> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8 </td></tr> <tr> <th>9 </th> <td>9</td> <td>1</td> <td>1</td> <td>9</td> <td>1</td> <td>1</td> <td>9</td> <td>1</td> <td>1</td> <td>9</td> <td>1</td> <td>1 </td></tr> <tr> <th>10 </th> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8</td> <td>4</td> <td>8</td> <td>8 </td></tr> <tr> <th>11 </th> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5</td> <td>1</td> <td>5</td> <td>5 </td></tr></tbody></table> </div> <div style="float:left; width: 50%; text-align: center; margin: 0 auto"> <p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3x^{2}+y^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>3</mn> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 3x^{2}+y^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7cefade515126f4c2c54ccdba7e883ab9c535c37" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.601ex; height:3.009ex;" alt="{\displaystyle 3x^{2}+y^{2}}"></span> </p> <table class="wikitable" style="margin:auto;clear:both;"> <tbody><tr> <th>y\x </th> <th>0</th> <th>1</th> <th>2</th> <th>3</th> <th>4</th> <th>5</th> <th>6</th> <th>7</th> <th>8</th> <th>9</th> <th>10</th> <th>11 </th></tr> <tr> <th>0 </th> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3 </td></tr> <tr> <th>1 </th> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4 </td></tr> <tr> <th>2 </th> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7 </td></tr> <tr> <th>3 </th> <td>9</td> <td>0</td> <td>9</td> <td>0</td> <td>9</td> <td>0</td> <td>9</td> <td>0</td> <td>9</td> <td>0</td> <td>9</td> <td>0 </td></tr> <tr> <th>4 </th> <td>4 </td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7 </td></tr> <tr> <th>5 </th> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4 </td></tr> <tr> <th>6 </th> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3 </td></tr> <tr> <th>7 </th> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4 </td></tr> <tr> <th>8 </th> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7 </td></tr> <tr> <th>9 </th> <td>9</td> <td>0</td> <td>9</td> <td>0</td> <td>9</td> <td>0</td> <td>9</td> <td>0</td> <td>9</td> <td>0</td> <td>9</td> <td>0 </td></tr> <tr> <th>10 </th> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7</td> <td>4</td> <td>7 </td></tr> <tr> <th>11 </th> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4</td> <td>1</td> <td>4 </td></tr></tbody></table> </div> <div style="clear:both;"></div> <div style="text-align: center; margin: 0 auto"> <p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3x^{2}-y^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>3</mn> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 3x^{2}-y^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e3f434a83bb047ca97e18f83e2082ec53d2d503" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.601ex; height:3.009ex;" alt="{\displaystyle 3x^{2}-y^{2}}"></span> </p> <table class="wikitable" style="margin:auto;clear:both;"> <tbody><tr> <th>y\x </th> <th>0</th> <th>1</th> <th>2</th> <th>3</th> <th>4</th> <th>5</th> <th>6</th> <th>7</th> <th>8</th> <th>9</th> <th>10</th> <th>11 </th></tr> <tr> <th>0 </th> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3 </td></tr> <tr> <th>1 </th> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2 </td></tr> <tr> <th>2 </th> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11 </td></tr> <tr> <th>3 </th> <td>3</td> <td>6</td> <td>3</td> <td>6</td> <td>3</td> <td>6</td> <td>3</td> <td>6</td> <td>3</td> <td>6</td> <td>3</td> <td>6 </td></tr> <tr> <th>4 </th> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11 </td></tr> <tr> <th>5 </th> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2 </td></tr> <tr> <th>6 </th> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3</td> <td>0</td> <td>3 </td></tr> <tr> <th>7 </th> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2 </td></tr> <tr> <th>8 </th> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11 </td></tr> <tr> <th>9 </th> <td>3</td> <td>6</td> <td>3</td> <td>6</td> <td>3</td> <td>6</td> <td>3</td> <td>6</td> <td>3</td> <td>6</td> <td>3</td> <td>6 </td></tr> <tr> <th>10 </th> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11</td> <td>8</td> <td>11 </td></tr> <tr> <th>11 </th> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2</td> <td>11</td> <td>2 </td></tr></tbody></table> </div> <div class="mw-heading mw-heading2"><h2 id="Spiegazione">Spiegazione</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Crivello_di_Atkin&veaction=edit&section=3" title="Modifica la sezione Spiegazione" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Crivello_di_Atkin&action=edit&section=3" title="Edit section's source code: Spiegazione"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>L'algoritmo ignora completamente tutti i numeri divisibili per due, tre o cinque. Tutti i numeri che in modulo 60 hanno resto 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, o 58 sono divisibili per due e non sono quindi primi. Tutti i numeri che in modulo 60 hanno resto 3, 9, 15, 21, 27, 33, 39, 45, 51, o 57 sono divisibili per tre e quindi non sono primi. Tutti i numeri che in modulo 60 hanno resto 5, 25, 35 o 55 sono divisibili per cinque e quindi non sono primi. Tutti questi resti vengono quindi ignorati. Rimangono i numeri che, modulo 12, hanno resto pari a 1, 5, 7, 11. </p><p>Tutti i numeri che in modulo 60 hanno resto 1, 13, 17, 29, 37, 41, 49, o 53 hanno in modulo 4 un resto uguale a 1 (1 o 5 modulo 12; se il resto fosse 9 sarebbero divisibili per 3). Questi numeri sono primi <a href="/wiki/Se_e_solo_se" title="Se e solo se">se e solo se</a> il numero di soluzioni di 4<i>x</i><sup>2</sup> + <i>y</i><sup>2</sup> = <i>n</i> è dispari ed il numero è <a href="/wiki/Intero_privo_di_quadrati" title="Intero privo di quadrati">privo di quadrati</a> (dimostrato come teorema 6.1 in <sup id="cite_ref-paper_1-1" class="reference"><a href="#cite_note-paper-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>). </p><p>Tutti i numeri che in modulo 60 hanno resto 7, 19, 31 o 43 hanno in modulo 6 un resto uguale a 1 (1 o 7 modulo 12). Questi numeri sono primi se e solo se il numero di soluzioni di 3<i>x</i><sup>2</sup> + <i>y</i><sup>2</sup> = <i>n</i> è dispari ed il numero è privo di quadrati (dimostrato come teorema 6.2 in <sup id="cite_ref-paper_1-2" class="reference"><a href="#cite_note-paper-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>). </p><p>Tutti i numeri che in modulo 60 hanno resto 11, 23, 47 o 59 hanno in modulo 12 un resto uguale a 11. Questi numeri sono primi se e solo se il numero di soluzioni di 3<i>x</i><sup>2</sup> − <i>y</i><sup>2</sup> = <i>n</i> è dispari ed il numero è privo di quadrati (dimostrato come teorema 6.3 in <sup id="cite_ref-paper_1-3" class="reference"><a href="#cite_note-paper-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>). </p><p>Nessun potenziale numero primo è divisibile per 2, 3 o 5 quindi non possono essere divisibili neanche per i loro quadrati. Ecco perché il controllo squarefree non include 2<sup>2</sup>, 3<sup>2</sup>, e 5<sup>2</sup>. </p> <div class="mw-heading mw-heading2"><h2 id="Complessità_computazionale"><span id="Complessit.C3.A0_computazionale"></span>Complessità computazionale</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Crivello_di_Atkin&veaction=edit&section=4" title="Modifica la sezione Complessità computazionale" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Crivello_di_Atkin&action=edit&section=4" title="Edit section's source code: Complessità computazionale"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Il crivello calcola primi fino a <i>N</i> con <a href="/wiki/O-grande" title="O-grande">O</a>(<i>N</i>/log log <i>N</i>) operazioni e soltanto <i>N</i><sup>1/2+o(1)</sup> bit di memoria. Il crivello di Eratostene compie O(<i>N</i>) operazioni e necessita di O(<i>N</i><sup>1/2</sup>(log log <i>N</i>)/log <i>N</i>) bit di memoria.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Note">Note</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Crivello_di_Atkin&veaction=edit&section=5" title="Modifica la sezione Note" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Crivello_di_Atkin&action=edit&section=5" title="Edit section's source code: Note"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-paper-1"><span class="mw-cite-backlink"><b>^</b> <sup><i><a href="#cite_ref-paper_1-0">a</a></i></sup> <sup><i><a href="#cite_ref-paper_1-1">b</a></i></sup> <sup><i><a href="#cite_ref-paper_1-2">c</a></i></sup> <sup><i><a href="#cite_ref-paper_1-3">d</a></i></sup></span> <span class="reference-text">A.O.L. Atkin, D.J. Bernstein, <a rel="nofollow" class="external text" href="https://cr.yp.to/papers/primesieves-19990826.pdf"><i>Prime sieves using binary quadratic forms</i></a>, <a rel="nofollow" class="external free" href="https://cr.yp.to/papers/primesieves-19990826.pdf">https://cr.yp.to/papers/primesieves-19990826.pdf</a> (1999). [Accessibile a tutti]<br />A.O.L. Atkin, D.J. Bernstein, <a rel="nofollow" class="external text" href="http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf"><i>Prime sieves using binary quadratic forms</i></a>, Math. Comp. <b>73</b> (2004), 1023-1030. [Più recente]</span> </li> <li id="cite_note-2"><a href="#cite_ref-2"><b>^</b></a> <span class="reference-text">Queste stime di complessità includono alcune semplici ottimizzazioni, come la <a href="/w/index.php?title=Wheel_factorization&action=edit&redlink=1" class="new" title="Wheel factorization (la pagina non esiste)">wheel factorization</a>, e la divisione in blocchi computazionali più piccoli.</span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="Voci_correlate">Voci correlate</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Crivello_di_Atkin&veaction=edit&section=6" title="Modifica la sezione Voci correlate" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Crivello_di_Atkin&action=edit&section=6" title="Edit section's source code: Voci correlate"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Crivello_di_Sundaram" title="Crivello di Sundaram">Crivello di Sundaram</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Collegamenti_esterni">Collegamenti esterni</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Crivello_di_Atkin&veaction=edit&section=7" title="Modifica la sezione Collegamenti esterni" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Crivello_di_Atkin&action=edit&section=7" title="Edit section's source code: Collegamenti esterni"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://cr.yp.to/primegen.html">An optimized implementation of the sieve</a> (in <a href="/wiki/C_(linguaggio)" class="mw-redirect" title="C (linguaggio)">C</a>)</li></ul> <style data-mw-deduplicate="TemplateStyles:r141815314">.mw-parser-output .navbox{border:1px solid #aaa;clear:both;margin:auto;padding:2px;width:100%}.mw-parser-output .navbox th{padding-left:1em;padding-right:1em;text-align:center}.mw-parser-output .navbox>tbody>tr:first-child>th{background:#ccf;font-size:90%;width:100%;color:var(--color-base,black)}.mw-parser-output .navbox_navbar{float:left;margin:0;padding:0 10px 0 0;text-align:left;width:6em}.mw-parser-output .navbox_title{font-size:110%}.mw-parser-output .navbox_abovebelow{background:#ddf;font-size:90%;font-weight:normal}.mw-parser-output .navbox_group{background:#ddf;font-size:90%;padding:0 10px;white-space:nowrap}.mw-parser-output .navbox_list{font-size:90%;width:100%}.mw-parser-output .navbox_list a{white-space:nowrap}html:not(.vector-feature-night-mode-enabled) .mw-parser-output .navbox_odd{background:#fdfdfd;color:var(--color-base,black)}html:not(.vector-feature-night-mode-enabled) .mw-parser-output .navbox_even{background:#f7f7f7;color:var(--color-base,black)}.mw-parser-output .navbox a.mw-selflink{color:var(--color-base,black)}.mw-parser-output .navbox_center{text-align:center}.mw-parser-output .navbox .navbox_image{padding-left:7px;vertical-align:middle;width:0}.mw-parser-output .navbox+.navbox{margin-top:-1px}.mw-parser-output .navbox .mw-collapsible-toggle{font-weight:normal;text-align:right;width:7em}body.skin--responsive .mw-parser-output .navbox_image img{max-width:none!important}.mw-parser-output .subnavbox{margin:-3px;width:100%}.mw-parser-output .subnavbox_group{background:#e6e6ff;padding:0 10px}@media screen{html.skin-theme-clientpref-night .mw-parser-output .navbox>tbody>tr:first-child>th{background:var(--background-color-interactive)!important}html.skin-theme-clientpref-night .mw-parser-output .navbox th{color:var(--color-base)!important}html.skin-theme-clientpref-night .mw-parser-output .navbox_abovebelow,html.skin-theme-clientpref-night .mw-parser-output .navbox_group{background:var(--background-color-interactive-subtle)!important}html.skin-theme-clientpref-night .mw-parser-output .subnavbox_group{background:var(--background-color-neutral-subtle)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbox>tbody>tr:first-child>th{background:var(--background-color-interactive)!important}html.skin-theme-clientpref-os .mw-parser-output .navbox th{color:var(--color-base)!important}html.skin-theme-clientpref-os .mw-parser-output .navbox_abovebelow,html.skin-theme-clientpref-os .mw-parser-output .navbox_group{background:var(--background-color-interactive-subtle)!important}html.skin-theme-clientpref-os .mw-parser-output .subnavbox_group{background:var(--background-color-neutral-subtle)!important}}</style><table class="navbox mw-collapsible mw-collapsed noprint metadata" id="navbox-Algebra"><tbody><tr><th colspan="3" style="background:#ffc0cb;"><div class="navbox_navbar"><div class="noprint plainlinks" style="background-color:transparent; padding:0; font-size:xx-small; color:var(--color-base, #000000); white-space:nowrap;"><a href="/wiki/Template:Algebra" title="Template:Algebra"><span title="Vai alla pagina del template">V</span></a> · <a href="/w/index.php?title=Discussioni_template:Algebra&action=edit&redlink=1" class="new" title="Discussioni template:Algebra (la pagina non esiste)"><span title="Discuti del template">D</span></a> · <a class="external text" href="https://it.wikipedia.org/w/index.php?title=Template:Algebra&action=edit"><span title="Modifica il template. Usa l'anteprima prima di salvare">M</span></a></div></div><span class="navbox_title"><a href="/wiki/Algebra" title="Algebra">Algebra</a></span></th></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Numero" title="Numero">Numeri</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Numero_naturale" title="Numero naturale">Naturali</a><b> ·</b> <a href="/wiki/Numero_intero" title="Numero intero">Interi</a><b> ·</b> <a href="/wiki/Numero_razionale" title="Numero razionale">Razionali</a><b> ·</b> <a href="/wiki/Numero_irrazionale" title="Numero irrazionale">Irrazionali</a><b> ·</b> <a href="/wiki/Numero_algebrico" title="Numero algebrico">Algebrici</a><b> ·</b> <a href="/wiki/Numero_trascendente" title="Numero trascendente">Trascendenti</a><b> ·</b> <a href="/wiki/Numero_reale" title="Numero reale">Reali</a><b> ·</b> <a href="/wiki/Numero_complesso" title="Numero complesso">Complessi</a><b> ·</b> <a href="/wiki/Numero_ipercomplesso" title="Numero ipercomplesso">Numero ipercomplesso</a><b> ·</b> <a href="/wiki/Numero_p-adico" title="Numero p-adico">Numero p-adico</a><b> ·</b> <a href="/wiki/Numero_duale" title="Numero duale">Duali</a><b> ·</b> <a href="/wiki/Numero_complesso_iperbolico" title="Numero complesso iperbolico">Complessi iperbolici</a></td><td rowspan="10" class="navbox_image"><figure class="mw-halign-right" typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics-p.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/58px-Nuvola_apps_edu_mathematics-p.svg.png" decoding="async" width="58" height="58" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/87px-Nuvola_apps_edu_mathematics-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/116px-Nuvola_apps_edu_mathematics-p.svg.png 2x" data-file-width="128" data-file-height="128" /></a><figcaption></figcaption></figure></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Principi fondamentali</th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Principio_d%27induzione" title="Principio d'induzione">Principio d'induzione</a><b> ·</b> <a href="/wiki/Principio_del_buon_ordinamento" title="Principio del buon ordinamento">Principio del buon ordinamento</a><b> ·</b> <a href="/wiki/Relazione_di_equivalenza" title="Relazione di equivalenza">Relazione di equivalenza</a><b> ·</b> <a href="/wiki/Relazione_d%27ordine" title="Relazione d'ordine">Relazione d'ordine</a><b> ·</b> <a href="/wiki/Associativit%C3%A0_della_potenza" title="Associatività della potenza">Associatività della potenza</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Algebra_elementare" title="Algebra elementare">Algebra elementare</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Equazione" title="Equazione">Equazione</a><b> ·</b> <a href="/wiki/Disequazione" title="Disequazione">Disequazione</a><b> ·</b> <a href="/wiki/Polinomio" title="Polinomio">Polinomio</a><b> ·</b> <a href="/wiki/Triangolo_di_Tartaglia" title="Triangolo di Tartaglia">Triangolo di Tartaglia</a><b> ·</b> <a href="/wiki/Teorema_binomiale" title="Teorema binomiale">Teorema binomiale</a><b> ·</b> <a href="/wiki/Teorema_del_resto" title="Teorema del resto">Teorema del resto</a><b> ·</b> <a href="/wiki/Lemma_di_Gauss_(polinomi)" title="Lemma di Gauss (polinomi)">Lemma di Gauss</a><b> ·</b> <a href="/wiki/Teorema_delle_radici_razionali" title="Teorema delle radici razionali">Teorema delle radici razionali</a><b> ·</b> <a href="/wiki/Regola_di_Ruffini" title="Regola di Ruffini">Regola di Ruffini</a><b> ·</b> <a href="/wiki/Criterio_di_Eisenstein" title="Criterio di Eisenstein">Criterio di Eisenstein</a><b> ·</b> <a href="/wiki/Criterio_di_Cartesio" title="Criterio di Cartesio">Criterio di Cartesio</a><b> ·</b> <a href="/wiki/Disequazione_con_il_valore_assoluto" title="Disequazione con il valore assoluto">Disequazione con il valore assoluto</a><b> ·</b> <a href="/wiki/Segno_(matematica)" title="Segno (matematica)">Segno</a><b> ·</b> <a href="/wiki/Metodo_di_Gauss-Seidel" title="Metodo di Gauss-Seidel">Metodo di Gauss-Seidel</a><b> ·</b> <a href="/wiki/Polinomio_simmetrico" title="Polinomio simmetrico">Polinomio simmetrico</a><b> ·</b> <a href="/wiki/Funzione_simmetrica" title="Funzione simmetrica">Funzione simmetrica</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Elementi di <a href="/wiki/Calcolo_combinatorio" title="Calcolo combinatorio">Calcolo combinatorio</a></th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Fattoriale" title="Fattoriale">Fattoriale</a><b> ·</b> <a href="/wiki/Permutazione" title="Permutazione">Permutazione</a><b> ·</b> <a href="/wiki/Disposizione" title="Disposizione">Disposizione</a><b> ·</b> <a href="/wiki/Combinazione" title="Combinazione">Combinazione</a><b> ·</b> <a href="/wiki/Dismutazione_(matematica)" title="Dismutazione (matematica)">Dismutazione</a><b> ·</b> <a href="/wiki/Principio_di_inclusione-esclusione" title="Principio di inclusione-esclusione">Principio di inclusione-esclusione</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Concetti fondamentali di <a href="/wiki/Teoria_dei_numeri" title="Teoria dei numeri">Teoria dei numeri</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><table class="subnavbox"><tbody><tr><th class="subnavbox_group">Primi</th><td colspan="1"><a href="/wiki/Numero_primo" title="Numero primo">Numero primo</a><b> ·</b> <a href="/wiki/Teorema_dell%27infinit%C3%A0_dei_numeri_primi" title="Teorema dell'infinità dei numeri primi">Teorema dell'infinità dei numeri primi</a><b> ·</b> <a href="/wiki/Crivello_di_Eratostene" title="Crivello di Eratostene">Crivello di Eratostene</a><b> ·</b> <a class="mw-selflink selflink">Crivello di Atkin</a><b> ·</b> <a href="/wiki/Test_di_primalit%C3%A0" title="Test di primalità">Test di primalità</a><b> ·</b> <a href="/wiki/Teorema_fondamentale_dell%27aritmetica" title="Teorema fondamentale dell'aritmetica">Teorema fondamentale dell'aritmetica</a></td></tr><tr><th class="subnavbox_group">Divisori</th><td colspan="1"><a href="/wiki/Interi_coprimi" title="Interi coprimi">Interi coprimi</a><b> ·</b> <a href="/wiki/Identit%C3%A0_di_B%C3%A9zout" title="Identità di Bézout">Identità di Bézout</a><b> ·</b> <a href="/wiki/Massimo_comun_divisore" title="Massimo comun divisore">MCD</a><b> ·</b> <a href="/wiki/Minimo_comune_multiplo" title="Minimo comune multiplo">mcm</a><b> ·</b> <a href="/wiki/Algoritmo_di_Euclide" title="Algoritmo di Euclide">Algoritmo di Euclide</a><b> ·</b> <a href="/wiki/Algoritmo_esteso_di_Euclide" title="Algoritmo esteso di Euclide">Algoritmo esteso di Euclide</a><b> ·</b> <a href="/wiki/Criteri_di_divisibilit%C3%A0" title="Criteri di divisibilità">Criteri di divisibilità</a><b> ·</b> <a href="/wiki/Divisore" title="Divisore">Divisore</a></td></tr><tr><th class="subnavbox_group"><a href="/wiki/Aritmetica_modulare" title="Aritmetica modulare">Aritmetica modulare</a></th><td colspan="1"><a href="/wiki/Teorema_cinese_del_resto" title="Teorema cinese del resto">Teorema cinese del resto</a><b> ·</b> <a href="/wiki/Piccolo_teorema_di_Fermat" title="Piccolo teorema di Fermat">Piccolo teorema di Fermat</a><b> ·</b> <a href="/wiki/Teorema_di_Eulero_(aritmetica_modulare)" title="Teorema di Eulero (aritmetica modulare)">Teorema di Eulero</a><b> ·</b> <a href="/wiki/Funzione_%CF%86_di_Eulero" title="Funzione φ di Eulero">Funzione φ di Eulero</a><b> ·</b> <a href="/wiki/Teorema_di_Wilson" title="Teorema di Wilson">Teorema di Wilson</a><b> ·</b> <a href="/wiki/Reciprocit%C3%A0_quadratica" title="Reciprocità quadratica">Reciprocità quadratica</a></td></tr></tbody></table></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Teoria_dei_gruppi" title="Teoria dei gruppi">Teoria dei gruppi</a></th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><table class="subnavbox"><tbody><tr><th class="subnavbox_group">Gruppi</th><td colspan="1"><a href="/wiki/Gruppo_(matematica)" title="Gruppo (matematica)">Gruppo</a> (<a href="/wiki/Gruppo_finito" title="Gruppo finito">finito</a><b> ·</b> <a href="/wiki/Gruppo_ciclico" title="Gruppo ciclico">ciclico</a><b> ·</b> <a href="/wiki/Gruppo_abeliano" title="Gruppo abeliano">abeliano</a>)<b> ·</b> <a href="/wiki/Gruppo_primario" title="Gruppo primario">Gruppo primario</a><b> ·</b> <a href="/wiki/Gruppo_quoziente" title="Gruppo quoziente">Gruppo quoziente</a><b> ·</b> <a href="/wiki/Gruppo_nilpotente" title="Gruppo nilpotente">Gruppo nilpotente</a><b> ·</b> <a href="/wiki/Gruppo_risolubile" title="Gruppo risolubile">Gruppo risolubile</a><b> ·</b> <a href="/wiki/Gruppo_simmetrico" title="Gruppo simmetrico">Gruppo simmetrico</a><b> ·</b> <a href="/wiki/Gruppo_diedrale" title="Gruppo diedrale">Gruppo diedrale</a><b> ·</b> <a href="/wiki/Gruppo_semplice" title="Gruppo semplice">Gruppo semplice</a><b> ·</b> <a href="/wiki/Gruppo_sporadico" title="Gruppo sporadico">Gruppo sporadico</a><b> ·</b> <a href="/wiki/Gruppo_mostro" title="Gruppo mostro">Gruppo mostro</a><b> ·</b> <a href="/wiki/Gruppo_di_Klein" title="Gruppo di Klein">Gruppo di Klein</a><b> ·</b> <a href="/wiki/Gruppo_dei_quaternioni" title="Gruppo dei quaternioni">Gruppo dei quaternioni</a><b> ·</b> <a href="/wiki/Gruppo_generale_lineare" title="Gruppo generale lineare">Gruppo generale lineare</a><b> ·</b> <a href="/wiki/Gruppo_ortogonale" title="Gruppo ortogonale">Gruppo ortogonale</a><b> ·</b> <a href="/wiki/Gruppo_unitario" title="Gruppo unitario">Gruppo unitario</a><b> ·</b> <a href="/wiki/Gruppo_unitario_speciale" title="Gruppo unitario speciale">Gruppo unitario speciale</a><b> ·</b> <a href="/wiki/Gruppo_residualmente_finito" title="Gruppo residualmente finito">Gruppo residualmente finito</a><b> ·</b> <a href="/wiki/Gruppo_spaziale" title="Gruppo spaziale">Gruppo spaziale</a><b> ·</b> <a href="/wiki/Gruppo_profinito" title="Gruppo profinito">Gruppo profinito</a><b> ·</b> <a href="/wiki/Out(Fn)" title="Out(Fn)">Out(F<sub>n</sub>)</a><b> ·</b> <a href="/wiki/Parola_(teoria_dei_gruppi)" title="Parola (teoria dei gruppi)">Parola</a><b> ·</b> <a href="/wiki/Prodotto_diretto" title="Prodotto diretto">Prodotto diretto</a><b> ·</b> <a href="/wiki/Prodotto_semidiretto" title="Prodotto semidiretto">Prodotto semidiretto</a><b> ·</b> <a href="/wiki/Prodotto_intrecciato" title="Prodotto intrecciato">Prodotto intrecciato</a></td></tr><tr><th class="subnavbox_group">Teoremi</th><td colspan="1"><a href="/wiki/Alternativa_di_Tits" title="Alternativa di Tits">Alternativa di Tits</a><b> ·</b> <a href="/wiki/Teorema_di_isomorfismo" title="Teorema di isomorfismo">Teorema di isomorfismo</a><b> ·</b> <a href="/wiki/Teorema_di_Lagrange_(teoria_dei_gruppi)" title="Teorema di Lagrange (teoria dei gruppi)">Teorema di Lagrange</a><b> ·</b> <a href="/wiki/Teorema_di_Cauchy_(teoria_dei_gruppi)" title="Teorema di Cauchy (teoria dei gruppi)">Teorema di Cauchy</a><b> ·</b> <a href="/wiki/Teoremi_di_Sylow" title="Teoremi di Sylow">Teoremi di Sylow</a><b> ·</b> <a href="/wiki/Teorema_di_Cayley" title="Teorema di Cayley">Teorema di Cayley</a><b> ·</b> <a href="/wiki/Gruppo_abeliano#Classificazione" title="Gruppo abeliano">Teorema di struttura dei gruppi abeliani finiti</a><b> ·</b> <a href="/wiki/Lemma_della_farfalla" title="Lemma della farfalla">Lemma della farfalla</a><b> ·</b> <a href="/wiki/Lemma_del_ping-pong" title="Lemma del ping-pong">Lemma del ping-pong</a><b> ·</b> <a href="/wiki/Classificazione_dei_gruppi_semplici_finiti" title="Classificazione dei gruppi semplici finiti">Classificazione dei gruppi semplici finiti</a></td></tr><tr><th class="subnavbox_group">Sottoinsiemi</th><td colspan="1"><a href="/wiki/Sottogruppo" title="Sottogruppo">Sottogruppo</a><b> ·</b> <a href="/wiki/Sottogruppo_normale" title="Sottogruppo normale">Sottogruppo normale</a><b> ·</b> <a href="/wiki/Sottogruppo_caratteristico" title="Sottogruppo caratteristico">Sottogruppo caratteristico</a><b> ·</b> <a href="/wiki/Sottogruppo_di_Frattini" title="Sottogruppo di Frattini">Sottogruppo di Frattini</a><b> ·</b> <a href="/wiki/Sottogruppo_di_torsione" title="Sottogruppo di torsione">Sottogruppo di torsione</a><b> ·</b> <a href="/wiki/Classe_laterale" title="Classe laterale">Classe laterale</a><b> ·</b> <a href="/wiki/Classe_di_coniugio" title="Classe di coniugio">Classe di coniugio</a><b> ·</b> <a href="/wiki/Serie_di_composizione" title="Serie di composizione">Serie di composizione</a></td></tr><tr><td colspan="2" class="navbox_center"><a href="/wiki/Omomorfismo_di_gruppi" title="Omomorfismo di gruppi">Omomorfismo</a><b> ·</b> <a href="/wiki/Isomorfismo_tra_gruppi" title="Isomorfismo tra gruppi">Isomorfismo</a><b> ·</b> <a href="/wiki/Automorfismo_interno" title="Automorfismo interno">Automorfismo interno</a><b> ·</b> <a href="/wiki/Automorfismo_esterno" title="Automorfismo esterno">Automorfismo esterno</a><b> ·</b> <a href="/wiki/Permutazione" title="Permutazione">Permutazione</a><b> ·</b> <a href="/wiki/Presentazione_di_un_gruppo" title="Presentazione di un gruppo">Presentazione di un gruppo</a><b> ·</b> <a href="/wiki/Azione_di_gruppo" title="Azione di gruppo">Azione di gruppo</a></td></tr></tbody></table></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Teoria_degli_anelli" title="Teoria degli anelli">Teoria degli anelli</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Anello_(algebra)" title="Anello (algebra)">Anello</a> (<a href="/wiki/Anello_artiniano" title="Anello artiniano">artiniano</a><b> ·</b> <a href="/wiki/Anello_noetheriano" title="Anello noetheriano">noetheriano</a><b> ·</b> <a href="/wiki/Anello_locale" title="Anello locale">locale</a>)<b> ·</b> <a href="/wiki/Caratteristica_(algebra)" title="Caratteristica (algebra)">Caratteristica</a><b> ·</b> <a href="/wiki/Ideale_(matematica)" title="Ideale (matematica)">Ideale</a> (<a href="/wiki/Ideale_primo" title="Ideale primo">primo</a><b> ·</b> <a href="/wiki/Ideale_massimale" title="Ideale massimale">massimale</a>)<b> ·</b> <a href="/wiki/Dominio_d%27integrit%C3%A0" title="Dominio d'integrità">Dominio</a> (<a href="/wiki/Dominio_a_fattorizzazione_unica" title="Dominio a fattorizzazione unica">a fattorizzazione unica</a><b> ·</b> <a href="/wiki/Dominio_ad_ideali_principali" title="Dominio ad ideali principali">a ideali principali</a><b> ·</b> <a href="/wiki/Dominio_euclideo" title="Dominio euclideo">euclideo</a>)<b> ·</b> <a href="/wiki/Matrice" title="Matrice">Matrice</a><b> ·</b> <a href="/wiki/Anello_semplice" title="Anello semplice">Anello semplice</a><b> ·</b> <a href="/wiki/Anello_degli_endomorfismi" title="Anello degli endomorfismi">Anello degli endomorfismi</a><b> ·</b> <a href="/wiki/Teorema_di_Artin-Wedderburn" title="Teorema di Artin-Wedderburn">Teorema di Artin-Wedderburn</a><b> ·</b> <a href="/wiki/Modulo_(algebra)" title="Modulo (algebra)">Modulo</a><b> ·</b> <a href="/wiki/Dominio_di_Dedekind" title="Dominio di Dedekind">Dominio di Dedekind</a><b> ·</b> <a href="/wiki/Estensione_di_anelli" title="Estensione di anelli">Estensione di anelli</a><b> ·</b> <a href="/wiki/Teorema_della_base_di_Hilbert" title="Teorema della base di Hilbert">Teorema della base di Hilbert</a><b> ·</b> <a href="/wiki/Anello_di_Gorenstein" title="Anello di Gorenstein">Anello di Gorenstein</a><b> ·</b> <a href="/wiki/Base_di_Gr%C3%B6bner" title="Base di Gröbner">Base di Gröbner</a><b> ·</b> <a href="/wiki/Prodotto_tensoriale" title="Prodotto tensoriale">Prodotto tensoriale</a><b> ·</b> <a href="/wiki/Primo_associato" title="Primo associato">Primo associato</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Teoria_dei_campi_(matematica)" class="mw-redirect" title="Teoria dei campi (matematica)">Teoria dei campi</a></th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><table class="subnavbox"><tbody><tr><td colspan="2" class="navbox_center"><a href="/wiki/Campo_(matematica)" title="Campo (matematica)">Campo</a><b> ·</b> <a href="/wiki/Polinomio_irriducibile" title="Polinomio irriducibile">Polinomio irriducibile</a><b> ·</b> <a href="/wiki/Polinomio_ciclotomico" title="Polinomio ciclotomico">Polinomio ciclotomico</a><b> ·</b> <a href="/wiki/Teorema_fondamentale_dell%27algebra" title="Teorema fondamentale dell'algebra">Teorema fondamentale dell'algebra</a><b> ·</b> <a href="/wiki/Campo_finito" title="Campo finito">Campo finito</a><b> ·</b> <a href="/wiki/Automorfismo" title="Automorfismo">Automorfismo</a><b> ·</b> <a href="/wiki/Endomorfismo_di_Frobenius" title="Endomorfismo di Frobenius">Endomorfismo di Frobenius</a></td></tr><tr><th class="subnavbox_group">Estensioni</th><td colspan="1"><a href="/wiki/Campo_di_spezzamento" title="Campo di spezzamento">Campo di spezzamento</a><b> ·</b> <a href="/wiki/Estensione_di_campi" title="Estensione di campi">Estensione di campi</a><b> ·</b> <a href="/wiki/Estensione_algebrica" title="Estensione algebrica">Estensione algebrica</a><b> ·</b> <a href="/wiki/Estensione_separabile" title="Estensione separabile">Estensione separabile</a><b> ·</b> <a href="/wiki/Chiusura_algebrica" title="Chiusura algebrica">Chiusura algebrica</a><b> ·</b> <a href="/wiki/Campo_di_numeri" title="Campo di numeri">Campo di numeri</a><b> ·</b> <a href="/wiki/Estensione_normale" title="Estensione normale">Estensione normale</a><b> ·</b> <a href="/wiki/Estensione_di_Galois" title="Estensione di Galois">Estensione di Galois</a><b> ·</b> <a href="/wiki/Estensione_abeliana" title="Estensione abeliana">Estensione abeliana</a><b> ·</b> <a href="/wiki/Estensione_ciclotomica" title="Estensione ciclotomica">Estensione ciclotomica</a><b> ·</b> <a href="/wiki/Teoria_di_Kummer" title="Teoria di Kummer">Teoria di Kummer</a></td></tr><tr><th class="subnavbox_group">Teoria di Galois</th><td colspan="1"><a href="/wiki/Gruppo_di_Galois" title="Gruppo di Galois">Gruppo di Galois</a><b> ·</b> <a href="/wiki/Teoria_di_Galois" title="Teoria di Galois">Teoria di Galois</a><b> ·</b> <a href="/wiki/Teorema_fondamentale_della_teoria_di_Galois" title="Teorema fondamentale della teoria di Galois">Teorema fondamentale della teoria di Galois</a><b> ·</b> <a href="/wiki/Teorema_di_Abel-Ruffini" title="Teorema di Abel-Ruffini">Teorema di Abel-Ruffini</a><b> ·</b> <a href="/wiki/Costruzioni_con_riga_e_compasso" title="Costruzioni con riga e compasso">Costruzioni con riga e compasso</a></td></tr></tbody></table></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Altre <a href="/wiki/Struttura_algebrica" title="Struttura algebrica">strutture algebriche</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Magma_(matematica)" title="Magma (matematica)">Magma</a><b> ·</b> <a href="/wiki/Semigruppo" title="Semigruppo">Semigruppo</a><b> ·</b> <a href="/wiki/Corpo_(matematica)" title="Corpo (matematica)">Corpo</a><b> ·</b> <a href="/wiki/Spazio_vettoriale" title="Spazio vettoriale">Spazio vettoriale</a><b> ·</b> <a href="/wiki/Algebra_su_campo" title="Algebra su campo">Algebra su campo</a><b> ·</b> <a href="/wiki/Algebra_di_Lie" title="Algebra di Lie">Algebra di Lie</a><b> ·</b> <a href="/wiki/Algebra_differenziale" title="Algebra differenziale">Algebra differenziale</a><b> ·</b> <a href="/wiki/Algebra_di_Clifford" title="Algebra di Clifford">Algebra di Clifford</a><b> ·</b> <a href="/wiki/Gruppo_topologico" title="Gruppo topologico">Gruppo topologico</a><b> ·</b> <a href="/wiki/Gruppo_ordinato" title="Gruppo ordinato">Gruppo ordinato</a><b> ·</b> <a href="/wiki/Quasi-anello" title="Quasi-anello">Quasi-anello</a><b> ·</b> <a href="/wiki/Algebra_di_Boole" title="Algebra di Boole">Algebra di Boole</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">argomenti</th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Teoria_delle_categorie" title="Teoria delle categorie">Teoria delle categorie</a><b> ·</b> <a href="/wiki/Algebra_lineare" title="Algebra lineare">Algebra lineare</a><b> ·</b> <a href="/wiki/Algebra_commutativa" title="Algebra commutativa">Algebra commutativa</a><b> ·</b> <a href="/wiki/Algebra_omologica" title="Algebra omologica">Algebra omologica</a><b> ·</b> <a href="/wiki/Algebra_astratta" title="Algebra astratta">Algebra astratta</a><b> ·</b> <a href="/wiki/Algebra_computazionale" class="mw-redirect" title="Algebra computazionale">Algebra computazionale</a><b> ·</b> <a href="/wiki/Algebra_differenziale" title="Algebra differenziale">Algebra differenziale</a><b> ·</b> <a href="/wiki/Algebra_universale" title="Algebra universale">Algebra universale</a></td></tr></tbody></table> <div class="noprint" style="width:100%; padding: 3px 0; display: flex; flex-wrap: wrap; row-gap: 4px; column-gap: 8px; box-sizing: border-box;"><div style="flex-grow: 1"><style data-mw-deduplicate="TemplateStyles:r140555418">.mw-parser-output .itwiki-template-occhiello{width:100%;line-height:25px;border:1px solid #CCF;background-color:#F0EEFF;box-sizing:border-box}.mw-parser-output .itwiki-template-occhiello-progetto{background-color:#FAFAFA}@media screen{html.skin-theme-clientpref-night .mw-parser-output .itwiki-template-occhiello{background-color:#202122;border-color:#54595D}html.skin-theme-clientpref-night .mw-parser-output .itwiki-template-occhiello-progetto{background-color:#282929}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .itwiki-template-occhiello{background-color:#202122;border-color:#54595D}html.skin-theme-clientpref-os .mw-parser-output .itwiki-template-occhiello-progetto{background-color:#282929}}</style><div class="itwiki-template-occhiello"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Crystal128-kmplot.svg" class="mw-file-description" title="Matematica"><img alt=" " src="//upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png" decoding="async" width="25" height="25" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/38px-Crystal128-kmplot.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/50px-Crystal128-kmplot.svg.png 2x" data-file-width="245" data-file-height="244" /></a></span> <b><a href="/wiki/Portale:Matematica" title="Portale:Matematica">Portale Matematica</a></b>: accedi alle voci di Wikipedia che trattano di matematica</div></div></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Estratto da "<a dir="ltr" href="https://it.wikipedia.org/w/index.php?title=Crivello_di_Atkin&oldid=135600914">https://it.wikipedia.org/w/index.php?title=Crivello_di_Atkin&oldid=135600914</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Categoria:Categorie" title="Categoria:Categorie">Categorie</a>: <ul><li><a href="/wiki/Categoria:Algoritmi_per_la_matematica" title="Categoria:Algoritmi per la matematica">Algoritmi per la matematica</a></li><li><a href="/wiki/Categoria:Numeri_primi" title="Categoria:Numeri primi">Numeri primi</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Categoria nascosta: <ul><li><a href="/wiki/Categoria:Informazioni_senza_fonte" title="Categoria:Informazioni senza fonte">Informazioni senza fonte</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> Questa pagina è stata modificata per l'ultima volta il 22 set 2023 alle 10:08.</li> <li id="footer-info-copyright">Il testo è disponibile secondo la <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.it">licenza Creative Commons Attribuzione-Condividi allo stesso modo</a>; possono applicarsi condizioni ulteriori. Vedi le <a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use/it">condizioni d'uso</a> per i dettagli.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/it">Informativa sulla privacy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:Sala_stampa/Wikipedia">Informazioni su Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:Avvertenze_generali">Avvertenze</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Codice di condotta</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Sviluppatori</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/it.wikipedia.org">Statistiche</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Dichiarazione sui cookie</a></li> <li id="footer-places-mobileview"><a href="//it.m.wikipedia.org/w/index.php?title=Crivello_di_Atkin&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Versione mobile</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-5ccf8d5c58-pvbwj","wgBackendResponseTime":125,"wgPageParseReport":{"limitreport":{"cputime":"0.210","walltime":"0.309","ppvisitednodes":{"value":1710,"limit":1000000},"postexpandincludesize":{"value":47238,"limit":2097152},"templateargumentsize":{"value":214,"limit":2097152},"expansiondepth":{"value":9,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":15342,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 152.345 1 -total"," 53.03% 80.783 1 Template:Algebra"," 51.19% 77.988 1 Template:Navbox"," 22.63% 34.473 1 Template:Portale"," 19.45% 29.626 1 Template:Senza_fonte"," 18.04% 27.486 1 Template:Chiarimento"," 13.01% 19.819 3 Template:Navbox_subgroup"," 10.81% 16.472 1 Template:Icona_argomento"," 4.18% 6.366 157 Template:·"," 1.47% 2.246 1 Template:Clear"]},"scribunto":{"limitreport-timeusage":{"value":"0.082","limit":"10.000"},"limitreport-memusage":{"value":1132607,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-7cc866bdbb-kwnm4","timestamp":"20241208141600","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Crivello di Atkin","url":"https:\/\/it.wikipedia.org\/wiki\/Crivello_di_Atkin","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1542201","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1542201","author":{"@type":"Organization","name":"Contributori ai progetti Wikimedia"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2006-10-08T18:19:35Z","dateModified":"2023-09-22T09:08:00Z","headline":"algoritmo matematico veloce e moderno per trovare numeri primi"}</script> </body> </html>