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="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Sieve of Pritchard - 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(/(?:^|; )enwikimwclientpreferences=([^;]+)/);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":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"aa87d125-fe5e-4967-884b-c183316f6fa8","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Sieve_of_Pritchard","wgTitle":"Sieve of Pritchard","wgCurRevisionId":1258376129,"wgRevisionId":1258376129,"wgArticleId":70873538,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Articles with example pseudocode","Primality tests","Sieve theory","Algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Sieve_of_Pritchard","wgRelevantArticleId":70873538,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia", "wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q112623438","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.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","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","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.quicksurveys.init","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</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=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%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=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <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 property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/b/b4/Sieve_of_Pritchard_animation.gif"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="988"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/b/b4/Sieve_of_Pritchard_animation.gif"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="659"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="527"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Sieve of Pritchard - 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="//en.m.wikipedia.org/wiki/Sieve_of_Pritchard"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Sieve_of_Pritchard&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 (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Sieve_of_Pritchard"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&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-Sieve_of_Pritchard rootpage-Sieve_of_Pritchard skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</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="Site"> <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="Main menu" > <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">Main menu</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">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" 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="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; 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/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</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="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search 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="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <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="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <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="Appearance" > <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">Appearance</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/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</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=Special:CreateAccount&returnto=Sieve+of+Pritchard" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</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=Special:UserLogin&returnto=Sieve+of+Pritchard" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</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="Log in and more options" > <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="Personal tools" > <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">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <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/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Sieve+of+Pritchard" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Sieve+of+Pritchard" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</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"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</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/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</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="Site"> <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="Contents" 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">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</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">(Top)</div> </a> </li> <li id="toc-Overview" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Overview"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Overview</span> </div> </a> <button aria-controls="toc-Overview-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Overview subsection</span> </button> <ul id="toc-Overview-sublist" class="vector-toc-list"> <li id="toc-Example" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Example"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Example</span> </div> </a> <ul id="toc-Example-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Pseudocode" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Pseudocode"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Pseudocode</span> </div> </a> <ul id="toc-Pseudocode-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementation" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implementation"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Implementation</span> </div> </a> <ul id="toc-Implementation-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Geometric_model" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Geometric_model"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Geometric model</span> </div> </a> <ul id="toc-Geometric_model-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Related_sieves" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Related_sieves"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Related sieves</span> </div> </a> <ul id="toc-Related_sieves-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>References</span> </div> </a> <ul id="toc-References-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="Contents" 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="Toggle the table of contents" > <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">Toggle the table of contents</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">Sieve of Pritchard</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="This article exist only in this language. Add the article for other languages" > <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-0" 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">Add languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> <div class="after-portlet after-portlet-lang"><span class="uls-after-portlet-link"></span><span class="wb-langlinks-add wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q112623438#sitelinks-wikipedia" title="Add interlanguage links" class="wbc-editpage">Add links</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="Namespaces"> <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/Sieve_of_Pritchard" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Sieve_of_Pritchard" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</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="Change language variant" > <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">English</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="Views"> <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/Sieve_of_Pritchard"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Sieve_of_Pritchard&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <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="Tools" > <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">Tools</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">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </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/Sieve_of_Pritchard"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Sieve_of_Pritchard&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Sieve_of_Pritchard" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Sieve_of_Pritchard" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Sieve_of_Pritchard&oldid=1258376129" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Sieve_of_Pritchard&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Sieve_of_Pritchard&id=1258376129&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSieve_of_Pritchard"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSieve_of_Pritchard"><span>Download QR code</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"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Sieve_of_Pritchard&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Sieve_of_Pritchard&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</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 other projects </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/Q112623438" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</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="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <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">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</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">From Wikipedia, the free encyclopedia</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="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Algorithm for generating prime numbers</div> <figure class="mw-halign-right" typeof="mw:File/Frame"><a href="/wiki/File:Sieve_of_Pritchard_animation.gif" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/b/b4/Sieve_of_Pritchard_animation.gif" decoding="async" width="425" height="350" class="mw-file-element" data-file-width="425" data-file-height="350" /></a><figcaption>Sieve of Pritchard: algorithm steps for primes up to 150</figcaption></figure> <p>In <a href="/wiki/Mathematics" title="Mathematics">mathematics</a>, the <b>sieve of Pritchard</b> is an <a href="/wiki/Algorithm" title="Algorithm">algorithm</a> for finding all <a href="/wiki/Prime_number" title="Prime number">prime numbers</a> up to a specified bound. Like the ancient <a href="/wiki/Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">sieve of Eratosthenes</a>, it has a simple conceptual basis in <a href="/wiki/Number_theory" title="Number theory">number theory</a>.<sup id="cite_ref-pritchard_explaining_1-0" class="reference"><a href="#cite_note-pritchard_explaining-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> It is especially suited to quick hand computation for small bounds. </p><p>Whereas the sieve of Eratosthenes marks off each non-prime for each of its prime factors, the sieve of Pritchard avoids considering almost all non-prime numbers by building progressively larger wheels, which represent the pattern of numbers not divisible by any of the primes processed thus far. It thereby achieves a better <a href="/wiki/Asymptotic_complexity" class="mw-redirect" title="Asymptotic complexity">asymptotic complexity</a>, and was the first sieve with a running time sublinear in the specified bound. Its asymptotic running-time has not been improved on, and it deletes fewer composites than any other known sieve. It was created in 1979 by Paul Pritchard.<sup id="cite_ref-pritchard_sublinear_2-0" class="reference"><a href="#cite_note-pritchard_sublinear-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p><p>Since Pritchard has created a number of other sieve algorithms for finding prime numbers,<sup id="cite_ref-pritchard_compact_3-0" class="reference"><a href="#cite_note-pritchard_compact-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-pritchard_tree_4-0" class="reference"><a href="#cite_note-pritchard_tree-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-pritchard_incremental_5-0" class="reference"><a href="#cite_note-pritchard_incremental-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> the sieve of Pritchard is sometimes singled out by being called <i>the wheel sieve</i> (by Pritchard himself<sup id="cite_ref-pritchard_explaining_1-1" class="reference"><a href="#cite_note-pritchard_explaining-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>) or <i>the dynamic wheel sieve</i>.<sup id="cite_ref-DJS_6-0" class="reference"><a href="#cite_note-DJS-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit&section=1" title="Edit section: Overview"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <a href="/wiki/Prime_number" title="Prime number">prime number</a> is a <a href="/wiki/Natural_number" title="Natural number">natural number</a> that has no natural number <a href="/wiki/Divisor" title="Divisor">divisors</a> other than the number <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 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}"></span> and itself. </p><p>To find all the prime numbers less than or equal to a given integer <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span>, a sieve algorithm examines a <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">set</a> of candidates in the range <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 2,3,...,N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2,3,...,N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8004ab589acb2523107397df1587a01feb2c02f0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.592ex; height:2.509ex;" alt="{\displaystyle 2,3,...,N}"></span>, and eliminates those that are not prime, leaving the primes at the end. The <a href="/wiki/Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">sieve of Eratosthenes</a> examines all of the range, first removing all multiples of the first prime <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 2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}"></span>, then of the next prime <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 3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/991e33c6e207b12546f15bdfee8b5726eafbbb2f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 3}"></span>, and so on. The sieve of Pritchard instead examines a subset of the range consisting of numbers that occur on successive wheels, which represent the pattern of numbers left after each successive prime is processed by the sieve of Eratosthenes. </p><p>For <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 i>0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>></mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i>0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f49f2878fd68a89c3da37eb537198e887cf0293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;" alt="{\displaystyle i>0}"></span> the <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 i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span>'th wheel <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 W_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7301a4cfd04d4f5db4549fdf23746a0d2ce9f387" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.993ex; height:2.509ex;" alt="{\displaystyle W_{i}}"></span> represents this pattern. It is the set of numbers between <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 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}"></span> and the product <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 P_{i}=p_{1}*p_{2}*...*p_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∗</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>∗</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>∗</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{i}=p_{1}*p_{2}*...*p_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d50b74b01ed0649f8b8a7ca22bb8787e9929a366" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.428ex; height:2.509ex;" alt="{\displaystyle P_{i}=p_{1}*p_{2}*...*p_{i}}"></span> of the first <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 i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> prime numbers that are not divisible by any of these prime numbers (and is said to have an associated <i>length</i> <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 P_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3ba1396129f7be3c7f828a571b6649e6807d10d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}"></span>). This is because adding <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 P_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3ba1396129f7be3c7f828a571b6649e6807d10d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}"></span> to a number doesn't change whether or not it is divisible by one of the first <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 i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> prime numbers, since the remainder on division by any one of these primes is unchanged. </p><p>So <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 W_{1}=\{1\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{1}=\{1\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/976fbea34aa2cbd20c8cf59058e8ad48c1da9b68" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.834ex; height:2.843ex;" alt="{\displaystyle W_{1}=\{1\}}"></span> with length <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 P_{1}=2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{1}=2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/20e0d0da80481ac481fb1412341109cc71b025ae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.807ex; height:2.509ex;" alt="{\displaystyle P_{1}=2}"></span> represents the pattern of odd numbers; <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 W_{2}=\{1,5\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>5</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{2}=\{1,5\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5b2ef967351acddb2131210d0d98a531e65fb6d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.03ex; height:2.843ex;" alt="{\displaystyle W_{2}=\{1,5\}}"></span> with length <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 P_{2}=6}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mn>6</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{2}=6}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/925083e02cc874126ef1cf76ccc4e8a83a0d94d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.807ex; height:2.509ex;" alt="{\displaystyle P_{2}=6}"></span> represents the pattern of numbers not divisible by <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 2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}"></span> or <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 3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/991e33c6e207b12546f15bdfee8b5726eafbbb2f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 3}"></span>; etc. Wheels are so-called because <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 W_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7301a4cfd04d4f5db4549fdf23746a0d2ce9f387" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.993ex; height:2.509ex;" alt="{\displaystyle W_{i}}"></span> can be usefully visualized as a circle of circumference <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 P_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3ba1396129f7be3c7f828a571b6649e6807d10d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}"></span> with its members marked at their corresponding distances from an origin. Then rolling the wheel along the number line marks points corresponding to successive numbers not divisible by one of the first <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 i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"></span> prime numbers. The animation shows <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 W_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/421467fcab2af38ddf3977b9adf66de8ef3abd57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{2}}"></span> being rolled up to 30. </p> <figure class="mw-halign-right" typeof="mw:File/Frame"><a href="/wiki/File:Rolling_wheel_animation.gif" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/4/4e/Rolling_wheel_animation.gif" decoding="async" width="998" height="117" class="mw-file-element" data-file-width="998" data-file-height="117" /></a><figcaption>Rolling the 2nd wheel up to 30.</figcaption></figure> <p>It's useful to define <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 W_{i}\rightarrow n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">→</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{i}\rightarrow n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eddbc39dc9c40baca8cecda094d6040278d90836" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.002ex; height:2.509ex;" alt="{\displaystyle W_{i}\rightarrow n}"></span> for <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 n>0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>></mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n>0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/27a6a5d982d54202a14f111cb8a49210501b2c96" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n>0}"></span> to be the result of rolling <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 W_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7301a4cfd04d4f5db4549fdf23746a0d2ce9f387" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.993ex; height:2.509ex;" alt="{\displaystyle W_{i}}"></span> up to <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 n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>. Then the animation generates <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 W_{2}\rightarrow 30=\{1,5,7,11,13,17,19,23,25,29\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo stretchy="false">→</mo> <mn>30</mn> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>5</mn> <mo>,</mo> <mn>7</mn> <mo>,</mo> <mn>11</mn> <mo>,</mo> <mn>13</mn> <mo>,</mo> <mn>17</mn> <mo>,</mo> <mn>19</mn> <mo>,</mo> <mn>23</mn> <mo>,</mo> <mn>25</mn> <mo>,</mo> <mn>29</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{2}\rightarrow 30=\{1,5,7,11,13,17,19,23,25,29\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57fde2b2e8dc078d4d7e63315580cce67c6c851d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:43.677ex; height:2.843ex;" alt="{\displaystyle W_{2}\rightarrow 30=\{1,5,7,11,13,17,19,23,25,29\}}"></span>. Note that up to <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 5^{2}-1=24}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>5</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mn>1</mn> <mo>=</mo> <mn>24</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 5^{2}-1=24}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/43b421e736a60ddb9105dd73fff6928a11ce14ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.643ex; height:2.843ex;" alt="{\displaystyle 5^{2}-1=24}"></span>, this consists only of <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 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}"></span> and the primes between <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 5}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>5</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 5}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/29483407999b8763f0ea335cf715a6a5e809f44b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 5}"></span> and <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 25}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>25</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 25}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a8acf6937f13156a1301ebb614c5364d16597e42" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 25}"></span>. </p><p>The sieve of Pritchard is derived from the observation<sup id="cite_ref-pritchard_explaining_1-2" class="reference"><a href="#cite_note-pritchard_explaining-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> that this holds generally: for all <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 i>0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>></mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i>0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f49f2878fd68a89c3da37eb537198e887cf0293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;" alt="{\displaystyle i>0}"></span>, the values in <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 W_{i}\rightarrow {(p_{i+1}^{2}-1)}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">→</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msubsup> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{i}\rightarrow {(p_{i+1}^{2}-1)}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/38ed08a96db8ca3b51723f1acfbf99c51ae4febf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:16.489ex; height:3.343ex;" alt="{\displaystyle W_{i}\rightarrow {(p_{i+1}^{2}-1)}}"></span> are <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 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}"></span> and the primes between <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 p_{i+1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p_{i+1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9577169925aad488f2b57f47eb556b22f89be6e2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:4.159ex; height:2.009ex;" alt="{\displaystyle p_{i+1}}"></span> and <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 p_{i+1}^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p_{i+1}^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/879b28e25d075e86e0fd2185753d3a6d2a20dd03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:4.159ex; height:3.343ex;" alt="{\displaystyle p_{i+1}^{2}}"></span>. It even holds for <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 i=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/31a682d568ee6a5fe51d76423186057f625ada5c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;" alt="{\displaystyle i=0}"></span>, where the wheel has length <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 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}"></span> and contains just <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 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}"></span> (representing all the natural numbers). So the sieve of Pritchard starts with the trivial wheel <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 W_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7f541f57fd799ba5137a2e50a1a728dde4306c06" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{0}}"></span> and builds successive wheels until the square of the wheel's first member after <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 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}"></span> is at least <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span>. Wheels grow very quickly, but only their values up to <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> are needed and generated. </p><p>It remains to find a method for generating the next wheel. Note in the animation that <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 W_{3}=\{1,5,7,11,13,17,19,23,25,29\}-\{5*1,5*5\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>5</mn> <mo>,</mo> <mn>7</mn> <mo>,</mo> <mn>11</mn> <mo>,</mo> <mn>13</mn> <mo>,</mo> <mn>17</mn> <mo>,</mo> <mn>19</mn> <mo>,</mo> <mn>23</mn> <mo>,</mo> <mn>25</mn> <mo>,</mo> <mn>29</mn> <mo fence="false" stretchy="false">}</mo> <mo>−</mo> <mo fence="false" stretchy="false">{</mo> <mn>5</mn> <mo>∗</mo> <mn>1</mn> <mo>,</mo> <mn>5</mn> <mo>∗</mo> <mn>5</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{3}=\{1,5,7,11,13,17,19,23,25,29\}-\{5*1,5*5\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/78971f0bdb9587379ef9763ae2a5952e896be3a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:52.977ex; height:2.843ex;" alt="{\displaystyle W_{3}=\{1,5,7,11,13,17,19,23,25,29\}-\{5*1,5*5\}}"></span> can be obtained by rolling <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 W_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/421467fcab2af38ddf3977b9adf66de8ef3abd57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{2}}"></span> up to <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 30}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>30</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 30}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5bbb9554d69ffa16547379e6d7dc2f0d76fbf637" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 30}"></span> and then removing <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 5}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>5</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 5}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/29483407999b8763f0ea335cf715a6a5e809f44b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 5}"></span> times each member of <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 W_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/421467fcab2af38ddf3977b9adf66de8ef3abd57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{2}}"></span>. This also holds generally: for all <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 i\geq 0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>≥</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i\geq 0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/405e1424cb9c4fc171c433a8e8f04b3e5938e366" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.063ex; height:2.343ex;" alt="{\displaystyle i\geq 0}"></span>, <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 W_{i+1}=(W_{i}\rightarrow P_{i+1})-\{p_{i+1}*w|w\in W_{i}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">→</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>−</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>∗</mo> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>w</mi> <mo>∈</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{i+1}=(W_{i}\rightarrow P_{i+1})-\{p_{i+1}*w|w\in W_{i}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/51dde2bfbf586bb456643f736b4f4b5216eefedb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.24ex; height:2.843ex;" alt="{\displaystyle W_{i+1}=(W_{i}\rightarrow P_{i+1})-\{p_{i+1}*w|w\in W_{i}\}}"></span>.<sup id="cite_ref-pritchard_explaining_1-3" class="reference"><a href="#cite_note-pritchard_explaining-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Rolling <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 W_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7301a4cfd04d4f5db4549fdf23746a0d2ce9f387" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.993ex; height:2.509ex;" alt="{\displaystyle W_{i}}"></span> past <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 P_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3ba1396129f7be3c7f828a571b6649e6807d10d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}"></span> just adds values to <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 W_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7301a4cfd04d4f5db4549fdf23746a0d2ce9f387" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.993ex; height:2.509ex;" alt="{\displaystyle W_{i}}"></span>, so the current wheel is first extended by getting each successive member starting with <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 w=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>w</mi> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle w=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19cbe03d2cb784a6fa6cd3727d4d2a71ed46fb74" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.925ex; height:2.176ex;" alt="{\displaystyle w=1}"></span>, adding <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 P_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3ba1396129f7be3c7f828a571b6649e6807d10d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}"></span> to it, and inserting the result in the set. Then the multiples of <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 p_{i+1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p_{i+1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9577169925aad488f2b57f47eb556b22f89be6e2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:4.159ex; height:2.009ex;" alt="{\displaystyle p_{i+1}}"></span> are deleted. Care must be taken to avoid a number being deleted that itself needs to be multiplied by <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 p_{i+1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p_{i+1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9577169925aad488f2b57f47eb556b22f89be6e2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:4.159ex; height:2.009ex;" alt="{\displaystyle p_{i+1}}"></span>. The sieve of Pritchard as originally presented<sup id="cite_ref-pritchard_sublinear_2-1" class="reference"><a href="#cite_note-pritchard_sublinear-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> does so by first skipping past successive members until finding the maximum one needed, and then doing the deletions in reverse order by working back through the set. This is the method used in the first animation above. A simpler approach is just to gather the multiples of <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 p_{i+1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p_{i+1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9577169925aad488f2b57f47eb556b22f89be6e2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:4.159ex; height:2.009ex;" alt="{\displaystyle p_{i+1}}"></span> in a list, and then delete them.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Another approach is given by Gries and Misra.<sup id="cite_ref-gries_misra_8-0" class="reference"><a href="#cite_note-gries_misra-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><p>If the main loop terminates with a wheel whose length is less than <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span>, it is extended up to <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> to generate the remaining primes. </p><p>The algorithm, for finding all primes up to <i>N</i>, is therefore as follows: </p> <ol><li>Start with a set <i>W</i>={1} and <i>length</i>=1 representing wheel 0, and prime <i>p</i>=2.</li> <li>As long as <i>p</i><sup>2</sup> <= <i>N</i>, do the following <ol><li>if <i>length</i> < <i>N</i> then <ol><li>extend <i>W</i> by repeatedly getting successive members <i>w</i> of <i>W</i> starting with 1 and inserting <i>length</i>+<i>w</i> into <i>W</i> as long as it doesn't exceed <i>p</i>*<i>length</i> or <i>N</i>;</li> <li>increase <i>length</i> to the minimum of <i>p</i>*<i>length</i> and <i>N</i>.</li></ol></li> <li>repeatedly delete <i>p</i> times each member of <i>W</i> by first finding the largest <= <i>length</i> and then working backwards.</li> <li>note the prime <i>p</i>, then set <i>p</i> to the next member of <i>W</i> after 1 (or 3 if <i>p</i> was 2).</li></ol></li> <li>if <i>length</i> < <i>N</i> then extend <i>W</i> to <i>N</i> by repeatedly getting successive members <i>w</i> of <i>W</i> starting with 1 and inserting <i>length</i>+<i>w</i> into <i>W</i> as long as it doesn't exceed <i>N</i>;</li> <li>On termination, the rest of the primes up to <i>N</i> are the members of <i>W</i> after 1.</li></ol> <div class="mw-heading mw-heading3"><h3 id="Example">Example</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit&section=2" title="Edit section: Example"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To find all the prime numbers less than or equal to 150, proceed as follows. </p><p>Start with wheel 0 with length 1, representing all natural numbers 1, 2, 3...: </p> <pre>  <b>1</b> </pre> <p>The first number after 1 for wheel 0 (when rolled) is 2; note it as a prime. Now form wheel 1 with length 2x1=2 by first extending wheel 0 up to 2 and then deleting 2 times each number in wheel 0, to get: </p> <pre>  <b>1 <span style="color:gray"><s>2</s></span></b> </pre> <p>The first number after 1 for wheel 1 (when rolled) is 3; note it as a prime. Now form wheel 2 with length 3x2=6 by first extending wheel 1 up to 6 and then deleting 3 times each number in wheel 1, to get </p> <pre>  <b>1 <span style="color:gray"><s>2</s></span> <span style="color:gray"><s>3</s></span> 5</b> </pre> <p>The first number after 1 for wheel 2 is 5; note it as a prime. Now form wheel 3 with length 5x6=30 by first extending wheel 2 up to 30 and then deleting 5 times each number in wheel 2 (in reverse order!), to get </p> <pre>  <b>1 <span style="color:gray"><s>2</s></span> <span style="color:gray"><s>3</s></span> <span style="color:gray"><s>5</s></span> 7 11 13 17 19 23 <span style="color:gray"><s>25</s></span> 29</b> </pre> <p>The first number after 1 for wheel 3 is 7; note it as a prime. Now wheel 4 has length 7x30=210, so we only extend wheel 3 up to our limit 150. (No further extending will be done now that the limit has been reached.) We then delete 7 times each number in wheel 3 until we exceed our limit 150, to get the elements in wheel 4 up to 150: </p> <pre>  <b>1 <span style="color:gray"><s>2</s></span> <span style="color:gray"><s>3</s></span> <span style="color:gray"><s>5</s></span> <span style="color:gray"><s>7</s></span> 11 13 17 19 23 <span style="color:gray"><s>25</s></span> 29 31 37 41 43 47 <span style="color:gray"><s>49</s></span> 53 59 61 67 71 73 <span style="color:gray"><s>77</s></span> 79 83 89 <span style="color:gray"><s>91</s></span> 97 101 103 107 109 113 <span style="color:gray"><s>119</s></span> 121 127 131 <span style="color:gray"><s>133</s></span> 137 139 143 149</b> </pre> <p>The first number after 1 for this partial wheel 4 is 11; note it as a prime. Since we've finished with rolling, we delete 11 times each number in the partial wheel 4 until we exceed our limit 150, to get the elements in wheel 5 up to 150: </p> <pre>  <b>1 <span style="color:gray"><s>2</s></span> <span style="color:gray"><s>3</s></span> <span style="color:gray"><s>5</s></span> <span style="color:gray"><s>7</s></span> <span style="color:gray"><s>11</s></span> 13 17 19 23 <span style="color:gray"><s>25</s></span> 29 31 37 41 43 47 <span style="color:gray"><s>49</s></span> 53 59 61 67 71 73 <span style="color:gray"><s>77</s></span> 79 83 89 <span style="color:gray"><s>91</s></span> 97 101 103 107 109 113 <span style="color:gray"><s>119</s></span> <span style="color:gray"><s>121</s></span> 127 131 <span style="color:gray"><s>133</s></span> 137 139 <span style="color:gray"><s>143</s></span> 149</b> </pre> <p>The first number after 1 for this partial wheel 5 is 13. Since 13 squared is at least our limit 150, we stop. The remaining numbers (other than 1) are the rest of the primes up to our limit 150. </p><p>Just 8 composite numbers are removed, once each. The rest of the numbers considered (other than 1) are prime. In comparison, the natural version of Eratosthenes sieve (stopping at the same point) removes composite numbers 184 times. </p> <div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit&section=3" title="Edit section: Pseudocode"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The sieve of Pritchard can be expressed in <a href="/wiki/Pseudocode" title="Pseudocode">pseudocode</a>, as follows:<sup id="cite_ref-pritchard_explaining_1-4" class="reference"><a href="#cite_note-pritchard_explaining-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p> <pre><b>algorithm</b> Sieve of Pritchard <b>is</b> <b>input</b>: an integer <i>N</i> >= 2. <b>output</b>: the set of prime numbers in {1,2,...,<i>N</i>}. <b>let</b> <i>W</i> and <i>Pr</i> be sets of <b><a href="/wiki/Integer_data_type" class="mw-redirect" title="Integer data type">integer</a></b> values, and all other variables <b><a href="/wiki/Integer_data_type" class="mw-redirect" title="Integer data type">integer</a></b> values. <i>k</i>, <i>W</i>, <i>length</i>, <i>p</i>, <i>Pr</i> := 1, {1}, 2, 3, {2}; {<b>invariant</b>: <i>p</i> = <i>p</i><sub><i>k</i>+1</sub> and <i>W</i> = <i>W</i><sub>k</sub> <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 \cap }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>∩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \cap }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d4e886e6f5a28a33e073fb108440c152ecfe2d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \cap }"></span> {1,2,...,<i>N</i>} and <i>length</i> = minimum of <i>P</i><sub>k</sub>,<i>N</i> and <i>Pr</i> = the primes up to <i>p</i><sub>k</sub>} <b>while</b> <i>p</i><sup>2</sup> <= <i>N</i> <b>do</b> <b>if</b> (<i>length</i> < <i>N</i>) <b>then</b> Extend <i>W</i>,<i>length</i> to minimum of <i>p</i>*<i>length</i>,<i>N</i>; Delete multiples of <i>p</i> from <i>W</i>; Insert <i>p</i> into <i>Pr</i>; <i>k</i>, <i>p</i> := <i>k</i>+1, next(<i>W</i>, 1) <b>if</b> (<i>length</i> < <i>N</i>) <b>then</b> Extend <i>W</i>,<i>length</i> to <i>N</i>; <b>return</b> <i>Pr</i> <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 \cup }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>∪</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \cup }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e8ff7d0293ad19b43524a133ae5129f3d71f2040" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \cup }"></span> <i>W</i> - {1}; </pre> <p>where next(<i>W</i>, w) is the next value in the ordered set <i>W</i> after <i>w</i>. </p> <pre><b>procedure</b> Extend <i>W</i>,<i>length</i> to <i>n</i> <b>is</b> {<b>in:</b> <i>W</i> = <i>W</i><sub>k</sub> and <i>length</i> = <i>P</i><sub>k</sub> and <i>n</i> > <i>length</i>} {<b>out:</b> <i>W</i> = <i>W</i><sub>k</sub><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 \rightarrow }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">→</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/53e574cc3aa5b4bf5f3f5906caf121a378eef08b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \rightarrow }"></span><i>n</i> and <i>length</i> = <i>n</i>} <b><a href="/wiki/Integer_data_type" class="mw-redirect" title="Integer data type">integer</a></b> w, x; <i>w</i>, <i>x</i> := 1, <i>length</i>+1; <b>while</b> <i>x</i> <= <i>n</i> <b>do</b> Insert <i>x</i> into <i>W</i>; <i>w</i> := next(<i>W</i>,<i>w</i>); <i>x</i> := <i>length</i> + <i>w</i>; <i>length</i> := <i>n</i>; </pre> <pre><b>procedure</b> Delete multiples of <i>p</i> from <i>W</i>,<i>length</i> <b>is</b> <b><a href="/wiki/Integer_data_type" class="mw-redirect" title="Integer data type">integer</a></b> w; <i>w</i> := <i>p</i>; <b>while</b> <i>p</i>*<i>w</i> <= <i>length</i> <b>do</b> <i>w</i> := next(<i>W</i>,<i>w</i>); <b>while</b> <i>w</i> > 1 <b>do</b> <i>w</i> := prev(<i>W</i>,<i>w</i>); Remove <i>p</i>*<i>w</i> from <i>W</i>; </pre> <p>where prev(<i>W</i>, w) is the previous value in the ordered set <i>W</i> before <i>w</i>. The algorithm can be initialized with <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 W_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7f541f57fd799ba5137a2e50a1a728dde4306c06" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{0}}"></span> instead of <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 W_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/74ab879909bd9762251f679bbb2fa738100baa45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{1}}"></span> at the minor complicaion of making next(<i>W</i>,1) a special case when <i>k</i> = 0. </p><p>This abstract algorithm uses ordered sets supporting the operations of insertion of a value greater than the maximum, deletion of a member, getting the next value after a member, and getting the previous value before a member. Using one of <a href="/wiki/Mertens%27_theorems" title="Mertens' theorems">Mertens' theorems</a> (the third) it can be shown to use <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 O(N/\log \log N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N/\log \log N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57f235a04a7f1a4285f810eb20fc5e3950889070" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.977ex; height:2.843ex;" alt="{\displaystyle O(N/\log \log N)}"></span> of these operations and additions and multiplications.<sup id="cite_ref-pritchard_sublinear_2-2" class="reference"><a href="#cite_note-pritchard_sublinear-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Implementation">Implementation</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit&section=4" title="Edit section: Implementation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>An array-based doubly-linked list <i>s</i> can be used to implement the ordered set <i>W</i>, with <i>s</i>[<i>w</i>] storing next(<i>W</i>,<i>w</i>) and <i>s</i>[<i>w</i>-1] storing prev(<i>W</i>,<i>w</i>). This permits each abstract operation to be implemented in a small number of operations. (The array can also be used to store the set <i>Pr</i> "for free".) Therefore the <a href="/wiki/Time_complexity" title="Time complexity">time complexity</a> of the sieve of Pritchard to calculate the primes up to <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> in the <a href="/wiki/Random_access_machine" class="mw-redirect" title="Random access machine">random access machine</a> model is <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 O(N/\log \log N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N/\log \log N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57f235a04a7f1a4285f810eb20fc5e3950889070" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.977ex; height:2.843ex;" alt="{\displaystyle O(N/\log \log N)}"></span> operations on words of size <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 O(\log N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/14eea297b4387decf341763c39dc038e05744272" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.005ex; height:2.843ex;" alt="{\displaystyle O(\log N)}"></span>. Pritchard also shows how multiplications can be eliminated by using very small multiplication tables,<sup id="cite_ref-pritchard_sublinear_2-3" class="reference"><a href="#cite_note-pritchard_sublinear-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> so the <a href="/wiki/Bit_complexity" class="mw-redirect" title="Bit complexity">bit complexity</a> is <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 O(N\log N/\log \log N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N\log N/\log \log N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9a89380901a1aa909dd89b18adf25f59cdee41fd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.787ex; height:2.843ex;" alt="{\displaystyle O(N\log N/\log \log N)}"></span> bit operations. </p><p>In the same model, the <a href="/wiki/Space_complexity" title="Space complexity">space complexity</a> is <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 O(N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/78484c5c26cfc97bb3b915418caa09454421e80b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.646ex; height:2.843ex;" alt="{\displaystyle O(N)}"></span> words, i.e., <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 O(N\log N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N\log N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/162285d42c319d5803cff2e5416a1f86d6baf394" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.456ex; height:2.843ex;" alt="{\displaystyle O(N\log N)}"></span> bits. The sieve of Eratosthenes requires only 1 bit for each candidate in the range 2 through <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span>, so its space complexity is lower at <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 O(N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/78484c5c26cfc97bb3b915418caa09454421e80b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.646ex; height:2.843ex;" alt="{\displaystyle O(N)}"></span> bits. Note that space needed for the primes is not counted, since they can printed or written to external storage as they are found. Pritchard<sup id="cite_ref-pritchard_sublinear_2-4" class="reference"><a href="#cite_note-pritchard_sublinear-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> presented a variant of his sieve that requires only <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 O(N/\log \log N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N/\log \log N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57f235a04a7f1a4285f810eb20fc5e3950889070" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.977ex; height:2.843ex;" alt="{\displaystyle O(N/\log \log N)}"></span> bits without compromising the sublinear time complexity, making it asymptotically superior to the natural version of the sieve of Eratostheses in both time and space. </p><p>However, the sieve of Eratostheses can be optimized to require much less memory by operating on successive segments of the natural numbers.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> Its space complexity can be reduced to <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 O({\sqrt {N}})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O({\sqrt {N}})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6a8566840a0a5d4480a0b8ed63d0717c3a89ec9a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.582ex; height:3.176ex;" alt="{\displaystyle O({\sqrt {N}})}"></span> bits without increasing its time complexity<sup id="cite_ref-pritchard_compact_3-1" class="reference"><a href="#cite_note-pritchard_compact-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> This means that in practice it can be used for much larger limits <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> than would otherwise fit in memory, and also take advantage of fast cache memory. For maximum speed it is also optimized using a small wheel to avoid sieving with the first few primes (although this does not change its asymptotic time complexity). Therefore the sieve of Pritchard is not competitive as a practical sieve over sufficiently large ranges. </p> <div class="mw-heading mw-heading2"><h2 id="Geometric_model">Geometric model</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit&section=5" title="Edit section: Geometric model"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Frame"><a href="/wiki/File:Building_the_wheels_up_to_wheel_3.gif" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/d/d4/Building_the_wheels_up_to_wheel_3.gif" decoding="async" width="314" height="282" class="mw-file-element" data-file-width="314" data-file-height="282" /></a><figcaption>Generating successive wheels up to <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 W_{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b87b911493067a5414c6bc6c4433ff3840062864" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{3}}"></span></figcaption></figure> <p>At the heart of the sieve of Pritchard is an algorithm for building successive wheels. It has a simple geometric model as follows: </p> <ol><li>Start with a circle of circumference 1 with a mark at 1</li> <li>To generate the next wheel: <ol><li>Go around the wheel and find (the distance to) the first mark after 1; call it p</li> <li>Create a new circle with p times the circumference of the current wheel</li> <li>Roll the current wheel around the new circle, marking it where a mark touches it</li> <li>Magnify the current wheel by p and remove the marks that coincide</li></ol></li></ol> <p>Note that for the first 2 iterations it is necessary to continue round the circle until 1 is reached again. </p><p>The first circle represents <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 W_{0}=\{1\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{0}=\{1\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/065d7db41774106ecb63c092b5ebff2179afe93e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.834ex; height:2.843ex;" alt="{\displaystyle W_{0}=\{1\}}"></span>, and successive circles represent wheels <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 W_{1},W_{2},...}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{1},W_{2},...}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d28d19725007c0cd3903a4ab4170c1bbbd5f578a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.278ex; height:2.509ex;" alt="{\displaystyle W_{1},W_{2},...}"></span>. The animation on the right shows this model in action up to <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 W_{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b87b911493067a5414c6bc6c4433ff3840062864" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{3}}"></span>. </p><p>It is apparent from the model that wheels are symmetric. This is because <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 P_{k}-w}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mo>−</mo> <mi>w</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{k}-w}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5969f8abe87b581045ce77397e1309b84f7d7a75" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.086ex; height:2.509ex;" alt="{\displaystyle P_{k}-w}"></span> is not divisible by one of the first <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 k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> primes if and only if <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 w}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>w</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle w}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}"></span> is not so divisible. It is possible to exploit this to avoid processing some composites, but at the cost of a more complex algorithm. </p> <div class="mw-heading mw-heading2"><h2 id="Related_sieves">Related sieves</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit&section=6" title="Edit section: Related sieves"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Once the wheel in the sieve of Pritchard reaches its maximum size, the remaining operations are equivalent to those performed by <a href="/wiki/Sieve_of_Eratosthenes#Euler's_sieve" title="Sieve of Eratosthenes">Euler's sieve</a>. </p><p>The sieve of Pritchard is unique in conflating the set of prime candidates with a dynamic wheel used to speed up the sifting process. But a separate static wheel (as frequently used to speed up the sieve of Eratosthenes) can give an <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 O(\log \log N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log \log N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fa2f6c9502c8747f6316e77d77d1d582e4262f65" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.364ex; height:2.843ex;" alt="{\displaystyle O(\log \log N)}"></span> speedup to the latter, or to linear sieves, provided it is large enough (as a function of <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span>). Examples are the use of the largest wheel of length not exceeding <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 {\sqrt {N}}/log^{2}N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>l</mi> <mi>o</mi> <msup> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {N}}/log^{2}N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ca97dd121b699fede66929897ce8377c9b31cdf3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.219ex; height:3.176ex;" alt="{\displaystyle {\sqrt {N}}/log^{2}N}"></span> to get a version of the sieve of Eratosthenes that takes <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 O(N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/78484c5c26cfc97bb3b915418caa09454421e80b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.646ex; height:2.843ex;" alt="{\displaystyle O(N)}"></span> additions and requires only <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 O({\sqrt {N}}/\log \log N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>N</mi> </msqrt> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O({\sqrt {N}}/\log \log N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2eaa039cb08a3d0ad97570aa2deea6fe845aceda" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.913ex; height:3.176ex;" alt="{\displaystyle O({\sqrt {N}}/\log \log N)}"></span> bits,<sup id="cite_ref-pritchard_compact_3-2" class="reference"><a href="#cite_note-pritchard_compact-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> and the speedup of the naturally linear <a href="/wiki/Sieve_of_Atkin" title="Sieve of Atkin">sieve of Atkin</a> to get a sublinear optimized version. </p><p>Bengalloun found a linear <i>smoothly incremental</i> sieve,<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> i.e., one that (in theory) can run indefinitely and takes a bounded number of operations to increment the current bound <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 N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span>. He also showed how to make it sublinear by adapting the sieve of Pritchard to incrementally build the next dynamic wheel while the current one is being used. Pritchard<sup id="cite_ref-pritchard_incremental_5-1" class="reference"><a href="#cite_note-pritchard_incremental-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> showed how to avoid multiplications, thereby obtaining the same asymptotic bit-complexity as the sieve of Pritchard. </p><p>Runciman provides a functional algorithm<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> inspired by the sieve of Pritchard. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit&section=7" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a></li> <li><a href="/wiki/Sieve_of_Atkin" title="Sieve of Atkin">Sieve of Atkin</a></li> <li><a href="/wiki/Sieve_theory" title="Sieve theory">Sieve theory</a></li> <li><a href="/wiki/Wheel_factorization" title="Wheel factorization">Wheel factorization</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Pritchard&action=edit&section=8" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-columns references-column-width reflist-columns-2"> <ol class="references"> <li id="cite_note-pritchard_explaining-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-pritchard_explaining_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-pritchard_explaining_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-pritchard_explaining_1-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-pritchard_explaining_1-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-pritchard_explaining_1-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFPritchard1982" class="citation journal cs1">Pritchard, Paul (1982). "Explaining the Wheel Sieve". <i>Acta Informatica</i>. <b>17</b> (4): 477–485. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00264164">10.1007/BF00264164</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122592488">122592488</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=Explaining+the+Wheel+Sieve&rft.volume=17&rft.issue=4&rft.pages=477-485&rft.date=1982&rft_id=info%3Adoi%2F10.1007%2FBF00264164&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A122592488%23id-name%3DS2CID&rft.aulast=Pritchard&rft.aufirst=Paul&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-pritchard_sublinear-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-pritchard_sublinear_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-pritchard_sublinear_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-pritchard_sublinear_2-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-pritchard_sublinear_2-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-pritchard_sublinear_2-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPritchard1981" class="citation journal cs1">Pritchard, Paul (1981). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F358527.358540">"A Sublinear Additive Sieve for Finding Prime Numbers"</a>. <i>Communications of the ACM</i>. <b>24</b> (1): 18–23. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F358527.358540">10.1145/358527.358540</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16526704">16526704</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Communications+of+the+ACM&rft.atitle=A+Sublinear+Additive+Sieve+for+Finding+Prime+Numbers&rft.volume=24&rft.issue=1&rft.pages=18-23&rft.date=1981&rft_id=info%3Adoi%2F10.1145%2F358527.358540&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A16526704%23id-name%3DS2CID&rft.aulast=Pritchard&rft.aufirst=Paul&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F358527.358540&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-pritchard_compact-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-pritchard_compact_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-pritchard_compact_3-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-pritchard_compact_3-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPritchard1983" class="citation journal cs1">Pritchard, Paul (1983). "Fast Compact Prime Number Sieves (Among Others)". <i>Journal of Algorithms</i>. <b>4</b> (4): 332–344. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-6774%2883%2990014-7">10.1016/0196-6774(83)90014-7</a>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1813%2F6313">1813/6313</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1068851">1068851</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Algorithms&rft.atitle=Fast+Compact+Prime+Number+Sieves+%28Among+Others%29&rft.volume=4&rft.issue=4&rft.pages=332-344&rft.date=1983&rft_id=info%3Ahdl%2F1813%2F6313&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A1068851%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1016%2F0196-6774%2883%2990014-7&rft.aulast=Pritchard&rft.aufirst=Paul&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-pritchard_tree-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-pritchard_tree_4-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPritchard1987" class="citation journal cs1">Pritchard, Paul (1987). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0167-6423%2887%2990024-4">"Linear prime-number sieves: A family tree"</a>. <i>Science of Computer Programming</i>. <b>9</b> (1): 17–35. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0167-6423%2887%2990024-4">10.1016/0167-6423(87)90024-4</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:44111749">44111749</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Science+of+Computer+Programming&rft.atitle=Linear+prime-number+sieves%3A+A+family+tree&rft.volume=9&rft.issue=1&rft.pages=17-35&rft.date=1987&rft_id=info%3Adoi%2F10.1016%2F0167-6423%2887%2990024-4&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A44111749%23id-name%3DS2CID&rft.aulast=Pritchard&rft.aufirst=Paul&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252F0167-6423%252887%252990024-4&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-pritchard_incremental-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-pritchard_incremental_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-pritchard_incremental_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPritchard1980" class="citation book cs1">Pritchard, Paul (1980). "On the prime example of programming". <i>Language Design and Programming Methodology</i>. Lecture Notes in Computer Science. Vol. 877. pp. 280–288. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.835">10.1.1.52.835</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-09745-7_5">10.1007/3-540-09745-7_5</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-09745-7" title="Special:BookSources/978-3-540-09745-7"><bdi>978-3-540-09745-7</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9214019">9214019</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=On+the+prime+example+of+programming&rft.btitle=Language+Design+and+Programming+Methodology&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=280-288&rft.date=1980&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.52.835%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A9214019%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1007%2F3-540-09745-7_5&rft.isbn=978-3-540-09745-7&rft.aulast=Pritchard&rft.aufirst=Paul&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-DJS-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-DJS_6-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDuntenJonesSorenson1996" class="citation journal cs1">Dunten, Brian; Jones, Julie; Sorenson, Jonathan (1996). "A Space-Efficient Fast Prime Number Sieve". <i>Information Processing Letters</i>. <b>59</b> (2): 79–84. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.3936">10.1.1.31.3936</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2896%2900099-3">10.1016/0020-0190(96)00099-3</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9385950">9385950</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+Processing+Letters&rft.atitle=A+Space-Efficient+Fast+Prime+Number+Sieve&rft.volume=59&rft.issue=2&rft.pages=79-84&rft.date=1996&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.31.3936%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A9385950%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1016%2F0020-0190%2896%2900099-3&rft.aulast=Dunten&rft.aufirst=Brian&rft.au=Jones%2C+Julie&rft.au=Sorenson%2C+Jonathan&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMairson1977" class="citation journal cs1">Mairson, Harry G. (1977). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F359810.359838">"Some new upper bounds on the generation of prime numbers"</a>. <i>Communications of the ACM</i>. <b>20</b> (9): 664–669. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F359810.359838">10.1145/359810.359838</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:20118576">20118576</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Communications+of+the+ACM&rft.atitle=Some+new+upper+bounds+on+the+generation+of+prime+numbers&rft.volume=20&rft.issue=9&rft.pages=664-669&rft.date=1977&rft_id=info%3Adoi%2F10.1145%2F359810.359838&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A20118576%23id-name%3DS2CID&rft.aulast=Mairson&rft.aufirst=Harry+G.&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F359810.359838&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-gries_misra-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-gries_misra_8-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGriesMisra1978" class="citation journal cs1">Gries, David; Misra, Jayadev (1978). "A linear sieve algorithm for finding prime numbers". <i>Communications of the ACM</i>. <b>21</b> (12): 999–1003. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F359657.359660">10.1145/359657.359660</a>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1813%2F6407">1813/6407</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11990373">11990373</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Communications+of+the+ACM&rft.atitle=A+linear+sieve+algorithm+for+finding+prime+numbers&rft.volume=21&rft.issue=12&rft.pages=999-1003&rft.date=1978&rft_id=info%3Ahdl%2F1813%2F6407&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A11990373%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F359657.359660&rft.aulast=Gries&rft.aufirst=David&rft.au=Misra%2C+Jayadev&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBaysHudson1977" class="citation journal cs1">Bays, Carter; Hudson, Richard H. (1977). "The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10<sup>12</sup>". <i>BIT</i>. <b>17</b> (2): 121–127. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01932283">10.1007/BF01932283</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122592488">122592488</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=BIT&rft.atitle=The+segmented+sieve+of+Eratosthenes+and+primes+in+arithmetic+progressions+to+10%3Csup%3E12%3C%2Fsup%3E&rft.volume=17&rft.issue=2&rft.pages=121-127&rft.date=1977&rft_id=info%3Adoi%2F10.1007%2FBF01932283&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A122592488%23id-name%3DS2CID&rft.aulast=Bays&rft.aufirst=Carter&rft.au=Hudson%2C+Richard+H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBengelloun2004" class="citation journal cs1">Bengelloun, S. A. (2004). "An incremental primal sieve". <i>Acta Informatica</i>. <b>23</b> (2): 119–125. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00289493">10.1007/BF00289493</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:20118576">20118576</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=An+incremental+primal+sieve&rft.volume=23&rft.issue=2&rft.pages=119-125&rft.date=2004&rft_id=info%3Adoi%2F10.1007%2FBF00289493&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A20118576%23id-name%3DS2CID&rft.aulast=Bengelloun&rft.aufirst=S.+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRunciman1997" class="citation journal cs1">Runciman, C. (1997). <a rel="nofollow" class="external text" href="https://eprints.whiterose.ac.uk/3784/1/runcimanc1.pdf">"Lazy Wheel Sieves and Spirals of Primes"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of Functional Programming</i>. <b>7</b> (2): 219–225. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0956796897002670">10.1017/S0956796897002670</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2422563">2422563</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Functional+Programming&rft.atitle=Lazy+Wheel+Sieves+and+Spirals+of+Primes&rft.volume=7&rft.issue=2&rft.pages=219-225&rft.date=1997&rft_id=info%3Adoi%2F10.1017%2FS0956796897002670&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A2422563%23id-name%3DS2CID&rft.aulast=Runciman&rft.aufirst=C.&rft_id=https%3A%2F%2Feprints.whiterose.ac.uk%2F3784%2F1%2Fruncimanc1.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Pritchard" class="Z3988"></span></span> </li> </ol></div> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Number-theoretic_algorithms" style="padding:3px"><table class="nowraplinks mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Number-theoretic_algorithms" title="Template:Number-theoretic algorithms"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Number-theoretic_algorithms" title="Template talk:Number-theoretic algorithms"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Number-theoretic_algorithms" title="Special:EditPage/Template:Number-theoretic algorithms"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Number-theoretic_algorithms" style="font-size:114%;margin:0 4em"><a href="/wiki/Number_theory" title="Number theory">Number-theoretic</a> <a href="/wiki/Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Primality_test" title="Primality test">Primality tests</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/AKS_primality_test" title="AKS primality test">AKS</a></li> <li><a href="/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test" title="Adleman–Pomerance–Rumely primality test">APR</a></li> <li><a href="/wiki/Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW</a></li> <li><a href="/wiki/Elliptic_curve_primality" title="Elliptic curve primality">Elliptic curve</a></li> <li><a href="/wiki/Pocklington_primality_test" title="Pocklington primality test">Pocklington</a></li> <li><a href="/wiki/Fermat_primality_test" title="Fermat primality test">Fermat</a></li> <li><a href="/wiki/Lucas_primality_test" title="Lucas primality test">Lucas</a></li> <li><i><a href="/wiki/Lucas%E2%80%93Lehmer_primality_test" title="Lucas–Lehmer primality test">Lucas–Lehmer</a></i></li> <li><i><a href="/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test" title="Lucas–Lehmer–Riesel test">Lucas–Lehmer–Riesel</a></i></li> <li><i><a href="/wiki/Proth%27s_theorem" title="Proth's theorem">Proth's theorem</a></i></li> <li><i><a href="/wiki/P%C3%A9pin%27s_test" title="Pépin's test">Pépin's</a></i></li> <li><a href="/wiki/Quadratic_Frobenius_test" title="Quadratic Frobenius test">Quadratic Frobenius</a></li> <li><a href="/wiki/Solovay%E2%80%93Strassen_primality_test" title="Solovay–Strassen primality test">Solovay–Strassen</a></li> <li><a href="/wiki/Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Generating_primes" class="mw-redirect" title="Generating primes">Prime-generating</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Sieve_of_Atkin" title="Sieve of Atkin">Sieve of Atkin</a></li> <li><a href="/wiki/Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a></li> <li><a class="mw-selflink selflink">Sieve of Pritchard</a></li> <li><a href="/wiki/Sieve_of_Sundaram" title="Sieve of Sundaram">Sieve of Sundaram</a></li> <li><a href="/wiki/Wheel_factorization" title="Wheel factorization">Wheel factorization</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Integer_factorization" title="Integer factorization">Integer factorization</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Continued_fraction_factorization" title="Continued fraction factorization">Continued fraction (CFRAC)</a></li> <li><a href="/wiki/Dixon%27s_factorization_method" title="Dixon's factorization method">Dixon's</a></li> <li><a href="/wiki/Lenstra_elliptic-curve_factorization" title="Lenstra elliptic-curve factorization">Lenstra elliptic curve (ECM)</a></li> <li><a href="/wiki/Euler%27s_factorization_method" title="Euler's factorization method">Euler's</a></li> <li><a href="/wiki/Pollard%27s_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho</a></li> <li><a href="/wiki/Pollard%27s_p_%E2%88%92_1_algorithm" title="Pollard's p − 1 algorithm"><i>p</i> − 1</a></li> <li><a href="/wiki/Williams%27s_p_%2B_1_algorithm" title="Williams's p + 1 algorithm"><i>p</i> + 1</a></li> <li><a href="/wiki/Quadratic_sieve" title="Quadratic sieve">Quadratic sieve (QS)</a></li> <li><a href="/wiki/General_number_field_sieve" title="General number field sieve">General number field sieve (GNFS)</a></li> <li><i><a href="/wiki/Special_number_field_sieve" title="Special number field sieve">Special number field sieve (SNFS)</a></i></li> <li><a href="/wiki/Rational_sieve" title="Rational sieve">Rational sieve</a></li> <li><a href="/wiki/Fermat%27s_factorization_method" title="Fermat's factorization method">Fermat's</a></li> <li><a href="/wiki/Shanks%27s_square_forms_factorization" title="Shanks's square forms factorization">Shanks's square forms</a></li> <li><a href="/wiki/Trial_division" title="Trial division">Trial division</a></li> <li><a href="/wiki/Shor%27s_algorithm" title="Shor's algorithm">Shor's</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Multiplication_algorithm" title="Multiplication algorithm">Multiplication</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Ancient_Egyptian_multiplication" title="Ancient Egyptian multiplication">Ancient Egyptian</a></li> <li><a href="/wiki/Long_multiplication" class="mw-redirect" title="Long multiplication">Long</a></li> <li><a href="/wiki/Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba</a></li> <li><a href="/wiki/Toom%E2%80%93Cook_multiplication" title="Toom–Cook multiplication">Toom–Cook</a></li> <li><a href="/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen</a></li> <li><a href="/wiki/F%C3%BCrer%27s_algorithm" class="mw-redirect" title="Fürer's algorithm">Fürer's</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Euclidean_division" title="Euclidean division">Euclidean</a> <a href="/wiki/Division_algorithm" title="Division algorithm">division</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_division" class="mw-redirect" title="Binary division">Binary</a></li> <li><a href="/wiki/Chunking_(division)" title="Chunking (division)">Chunking</a></li> <li><a href="/wiki/Fourier_division" title="Fourier division">Fourier</a></li> <li><a href="/wiki/Goldschmidt_division" class="mw-redirect" title="Goldschmidt division">Goldschmidt</a></li> <li><a href="/wiki/Newton%E2%80%93Raphson_division" class="mw-redirect" title="Newton–Raphson division">Newton-Raphson</a></li> <li><a href="/wiki/Long_division" title="Long division">Long</a></li> <li><a href="/wiki/Short_division" title="Short division">Short</a></li> <li><a href="/wiki/SRT_division" class="mw-redirect" title="SRT division">SRT</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Discrete_logarithm" title="Discrete logarithm">Discrete logarithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Baby-step_giant-step" title="Baby-step giant-step">Baby-step giant-step</a></li> <li><a href="/wiki/Pollard%27s_rho_algorithm_for_logarithms" title="Pollard's rho algorithm for logarithms">Pollard rho</a></li> <li><a href="/wiki/Pollard%27s_kangaroo_algorithm" title="Pollard's kangaroo algorithm">Pollard kangaroo</a></li> <li><a href="/wiki/Pohlig%E2%80%93Hellman_algorithm" title="Pohlig–Hellman algorithm">Pohlig–Hellman</a></li> <li><a href="/wiki/Index_calculus_algorithm" title="Index calculus algorithm">Index calculus</a></li> <li><a href="/wiki/Function_field_sieve" title="Function field sieve">Function field sieve</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">Greatest common divisor</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_GCD_algorithm" title="Binary GCD algorithm">Binary</a></li> <li><a href="/wiki/Euclidean_algorithm" title="Euclidean algorithm">Euclidean</a></li> <li><a href="/wiki/Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">Extended Euclidean</a></li> <li><a href="/wiki/Lehmer%27s_GCD_algorithm" title="Lehmer's GCD algorithm">Lehmer's</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Quadratic_residue" title="Quadratic residue">Modular square root</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cipolla%27s_algorithm" title="Cipolla's algorithm">Cipolla</a></li> <li><a href="/wiki/Pocklington%27s_algorithm" title="Pocklington's algorithm">Pocklington's</a></li> <li><a href="/wiki/Tonelli%E2%80%93Shanks_algorithm" title="Tonelli–Shanks algorithm">Tonelli–Shanks</a></li> <li><a href="/wiki/Berlekamp%E2%80%93Rabin_algorithm" title="Berlekamp–Rabin algorithm">Berlekamp</a></li> <li><a href="/wiki/Kunerth%27s_algorithm" title="Kunerth's algorithm">Kunerth</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other algorithms</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Chakravala_method" title="Chakravala method">Chakravala</a></li> <li><a href="/wiki/Cornacchia%27s_algorithm" title="Cornacchia's algorithm">Cornacchia</a></li> <li><a href="/wiki/Exponentiation_by_squaring" title="Exponentiation by squaring">Exponentiation by squaring</a></li> <li><a href="/wiki/Integer_square_root" title="Integer square root">Integer square root</a></li> <li><a href="/wiki/Integer_relation_algorithm" title="Integer relation algorithm">Integer relation</a> (<a href="/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" title="Lenstra–Lenstra–Lovász lattice basis reduction algorithm">LLL</a>; <a href="/wiki/Korkine%E2%80%93Zolotarev_lattice_basis_reduction_algorithm" title="Korkine–Zolotarev lattice basis reduction algorithm">KZ</a>)</li> <li><a href="/wiki/Modular_exponentiation" title="Modular exponentiation">Modular exponentiation</a></li> <li><a href="/wiki/Montgomery_reduction" class="mw-redirect" title="Montgomery reduction">Montgomery reduction</a></li> <li><a href="/wiki/Schoof%27s_algorithm" title="Schoof's algorithm">Schoof</a></li> <li><a href="/wiki/Trachtenberg_system" title="Trachtenberg system">Trachtenberg system</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div> <ul><li><i>Italics</i> indicate that algorithm is for numbers of special forms</li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Sieve_of_Pritchard&oldid=1258376129">https://en.wikipedia.org/w/index.php?title=Sieve_of_Pritchard&oldid=1258376129</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Primality_tests" title="Category:Primality tests">Primality tests</a></li><li><a href="/wiki/Category:Sieve_theory" title="Category:Sieve theory">Sieve theory</a></li><li><a href="/wiki/Category:Algorithms" title="Category:Algorithms">Algorithms</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Articles_with_example_pseudocode" title="Category:Articles with example pseudocode">Articles with example pseudocode</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"> This page was last edited on 19 November 2024, at 10:27<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Sieve_of_Pritchard&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</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-7c5987fdcc-wsf7j","wgBackendResponseTime":171,"wgPageParseReport":{"limitreport":{"cputime":"0.387","walltime":"0.863","ppvisitednodes":{"value":1676,"limit":1000000},"postexpandincludesize":{"value":46220,"limit":2097152},"templateargumentsize":{"value":795,"limit":2097152},"expansiondepth":{"value":8,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":57593,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 369.822 1 -total"," 51.13% 189.074 1 Template:Reflist"," 38.89% 143.839 10 Template:Cite_journal"," 23.71% 87.694 1 Template:Number_theoretic_algorithms"," 21.33% 78.879 1 Template:Navbox"," 20.84% 77.059 1 Template:Short_description"," 12.41% 45.899 2 Template:Pagetype"," 5.26% 19.450 3 Template:Main_other"," 4.63% 17.138 1 Template:SDcat"," 1.56% 5.754 1 Template:Cite_book"]},"scribunto":{"limitreport-timeusage":{"value":"0.198","limit":"10.000"},"limitreport-memusage":{"value":5161428,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-qdcp7","timestamp":"20241122161702","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Sieve of Pritchard","url":"https:\/\/en.wikipedia.org\/wiki\/Sieve_of_Pritchard","sameAs":"http:\/\/www.wikidata.org\/entity\/Q112623438","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q112623438","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2022-05-26T07:04:45Z","dateModified":"2024-11-19T10:27:10Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/b\/b4\/Sieve_of_Pritchard_animation.gif","headline":"algorithm for generating prime numbers"}</script> </body> </html>