CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Sieve of Eratosthenes - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled 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":"59cc25b6-1c7c-4535-a9fd-42c34533f890","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Sieve_of_Eratosthenes","wgTitle":"Sieve of Eratosthenes","wgCurRevisionId":1273069038,"wgRevisionId":1273069038,"wgArticleId":73415,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles containing Greek-language text","Articles with short description","Short description matches Wikidata","Articles containing Ancient Greek (to 1453)-language text","Articles with example pseudocode","Primality tests","Sieve theory","Algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Sieve_of_Eratosthenes","wgRelevantArticleId":73415,"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,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q177898","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","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","ext.scribunto.logs","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.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=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.16"> <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/9/94/Animation_Sieve_of_Eratosth.gif"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="995"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/9/94/Animation_Sieve_of_Eratosth.gif"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="663"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="531"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Sieve of Eratosthenes - 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_Eratosthenes"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Sieve_of_Eratosthenes&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_Eratosthenes"> <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_Eratosthenes rootpage-Sieve_of_Eratosthenes 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" title="Main menu" > <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><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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+Eratosthenes" 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+Eratosthenes" 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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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+Eratosthenes" 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+Eratosthenes" 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-Algorithm_and_variants" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Algorithm_and_variants"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Algorithm and variants</span> </div> </a> <button aria-controls="toc-Algorithm_and_variants-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 Algorithm and variants subsection</span> </button> <ul id="toc-Algorithm_and_variants-sublist" class="vector-toc-list"> <li id="toc-Pseudocode" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Pseudocode"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Pseudocode</span> </div> </a> <ul id="toc-Pseudocode-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Segmented_sieve" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Segmented_sieve"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Segmented sieve</span> </div> </a> <ul id="toc-Segmented_sieve-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Incremental_sieve" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Incremental_sieve"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Incremental sieve</span> </div> </a> <ul id="toc-Incremental_sieve-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Algorithmic_complexity" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Algorithmic_complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Algorithmic complexity</span> </div> </a> <ul id="toc-Algorithmic_complexity-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Euler's_sieve" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Euler's_sieve"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Euler's sieve</span> </div> </a> <ul id="toc-Euler's_sieve-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">5</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">6</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>External links</span> </div> </a> <ul id="toc-External_links-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" title="Table of Contents" > <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 Eratosthenes</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="Go to an article in another language. Available in 62 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-62" 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">62 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%BA%D8%B1%D8%A8%D8%A7%D9%84_%D8%A5%D8%B1%D8%A7%D8%AA%D9%88%D8%B3%D8%AA%D9%8A%D9%86%D8%B3" title="غربال إراتوستينس – Arabic" lang="ar" hreflang="ar" data-title="غربال إراتوستينس" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Eratosfen_%C9%99l%C9%99yi" title="Eratosfen ələyi – Azerbaijani" lang="az" hreflang="az" data-title="Eratosfen ələyi" data-language-autonym="Azərbaycanca" data-language-local-name="Azerbaijani" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-bn mw-list-item"><a href="https://bn.wikipedia.org/wiki/%E0%A6%8F%E0%A6%B0%E0%A6%BE%E0%A6%A4%E0%A7%8B%E0%A6%B8%E0%A7%8D%E0%A6%A5%E0%A7%87%E0%A6%A8%E0%A7%87%E0%A6%B8_%E0%A6%9B%E0%A6%BE%E0%A6%95%E0%A6%A8%E0%A6%BF" title="এরাতোস্থেনেস ছাকনি – Bangla" lang="bn" hreflang="bn" data-title="এরাতোস্থেনেস ছাকনি" data-language-autonym="বাংলা" data-language-local-name="Bangla" class="interlanguage-link-target"><span>বাংলা</span></a></li><li class="interlanguage-link interwiki-ba mw-list-item"><a href="https://ba.wikipedia.org/wiki/%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD_%D1%81%D0%B5%D0%BB%D1%82%D3%99%D1%80%D0%B5" title="Эратосфен селтәре – Bashkir" lang="ba" hreflang="ba" data-title="Эратосфен селтәре" data-language-autonym="Башҡортса" data-language-local-name="Bashkir" class="interlanguage-link-target"><span>Башҡортса</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%BD%D0%B0_%D0%95%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%82%D0%B5%D0%BD" title="Решето на Ератостен – Bulgarian" lang="bg" hreflang="bg" data-title="Решето на Ератостен" data-language-autonym="Български" data-language-local-name="Bulgarian" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-bs mw-list-item"><a href="https://bs.wikipedia.org/wiki/Eratostenovo_sito" title="Eratostenovo sito – Bosnian" lang="bs" hreflang="bs" data-title="Eratostenovo sito" data-language-autonym="Bosanski" data-language-local-name="Bosnian" class="interlanguage-link-target"><span>Bosanski</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Sed%C3%A0s_d%27Erat%C3%B2stenes" title="Sedàs d'Eratòstenes – Catalan" lang="ca" hreflang="ca" data-title="Sedàs d'Eratòstenes" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Eratosthenovo_s%C3%ADto" title="Eratosthenovo síto – Czech" lang="cs" hreflang="cs" data-title="Eratosthenovo síto" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Eratosthenes%27_si" title="Eratosthenes' si – Danish" lang="da" hreflang="da" data-title="Eratosthenes' si" data-language-autonym="Dansk" data-language-local-name="Danish" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes" title="Sieb des Eratosthenes – German" lang="de" hreflang="de" data-title="Sieb des Eratosthenes" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Eratosthenese_s%C3%B5el" title="Eratosthenese sõel – Estonian" lang="et" hreflang="et" data-title="Eratosthenese sõel" data-language-autonym="Eesti" data-language-local-name="Estonian" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%9A%CF%8C%CF%83%CE%BA%CE%B9%CE%BD%CE%BF_%CF%84%CE%BF%CF%85_%CE%95%CF%81%CE%B1%CF%84%CE%BF%CF%83%CE%B8%CE%AD%CE%BD%CE%B7" title="Κόσκινο του Ερατοσθένη – Greek" lang="el" hreflang="el" data-title="Κόσκινο του Ερατοσθένη" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes" title="Criba de Eratóstenes – Spanish" lang="es" hreflang="es" data-title="Criba de Eratóstenes" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Kribrilo_de_Eratosteno" title="Kribrilo de Eratosteno – Esperanto" lang="eo" hreflang="eo" data-title="Kribrilo de Eratosteno" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Eratostenesen_bahea" title="Eratostenesen bahea – Basque" lang="eu" hreflang="eu" data-title="Eratostenesen bahea" data-language-autonym="Euskara" data-language-local-name="Basque" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%BA%D8%B1%D8%A8%D8%A7%D9%84_%D8%A7%D8%B1%D8%A7%D8%AA%D9%88%D8%B3%D8%AA%D9%86" title="غربال اراتوستن – Persian" lang="fa" hreflang="fa" data-title="غربال اراتوستن" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne" title="Crible d'Ératosthène – French" lang="fr" hreflang="fr" data-title="Crible d'Ératosthène" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes" title="Criba de Eratóstenes – Galician" lang="gl" hreflang="gl" data-title="Criba de Eratóstenes" data-language-autonym="Galego" data-language-local-name="Galician" class="interlanguage-link-target"><span>Galego</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4" title="에라토스테네스의 체 – Korean" lang="ko" hreflang="ko" data-title="에라토스테네스의 체" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D4%B7%D6%80%D5%A1%D5%BF%D5%B8%D5%BD%D5%A9%D5%A5%D5%B6%D5%A5%D5%BD%D5%AB_%D5%B4%D5%A1%D5%B2" title="Էրատոսթենեսի մաղ – Armenian" lang="hy" hreflang="hy" data-title="Էրատոսթենեսի մաղ" data-language-autonym="Հայերեն" data-language-local-name="Armenian" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Eratostenovo_sito" title="Eratostenovo sito – Croatian" lang="hr" hreflang="hr" data-title="Eratostenovo sito" data-language-autonym="Hrvatski" data-language-local-name="Croatian" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-io mw-list-item"><a href="https://io.wikipedia.org/wiki/Eratostenana_sivo" title="Eratostenana sivo – Ido" lang="io" hreflang="io" data-title="Eratostenana sivo" data-language-autonym="Ido" data-language-local-name="Ido" class="interlanguage-link-target"><span>Ido</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Tapis_Eratosthenes" title="Tapis Eratosthenes – Indonesian" lang="id" hreflang="id" data-title="Tapis Eratosthenes" data-language-autonym="Bahasa Indonesia" data-language-local-name="Indonesian" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Crivello_di_Eratostene" title="Crivello di Eratostene – Italian" lang="it" hreflang="it" data-title="Crivello di Eratostene" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%94%D7%A0%D7%A4%D7%94_%D7%A9%D7%9C_%D7%90%D7%A8%D7%98%D7%95%D7%A1%D7%AA%D7%A0%D7%A1" title="הנפה של ארטוסתנס – Hebrew" lang="he" hreflang="he" data-title="הנפה של ארטוסתנס" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ka mw-list-item"><a href="https://ka.wikipedia.org/wiki/%E1%83%94%E1%83%A0%E1%83%90%E1%83%A2%E1%83%9D%E1%83%A1%E1%83%97%E1%83%94%E1%83%9C%E1%83%94%E1%83%A1_%E1%83%A1%E1%83%90%E1%83%AA%E1%83%94%E1%83%A0%E1%83%98" title="ერატოსთენეს საცერი – Georgian" lang="ka" hreflang="ka" data-title="ერატოსთენეს საცერი" data-language-autonym="ქართული" data-language-local-name="Georgian" class="interlanguage-link-target"><span>ქართული</span></a></li><li class="interlanguage-link interwiki-la mw-list-item"><a href="https://la.wikipedia.org/wiki/Cribrum_Eratosthenis" title="Cribrum Eratosthenis – Latin" lang="la" hreflang="la" data-title="Cribrum Eratosthenis" data-language-autonym="Latina" data-language-local-name="Latin" class="interlanguage-link-target"><span>Latina</span></a></li><li class="interlanguage-link interwiki-lv mw-list-item"><a href="https://lv.wikipedia.org/wiki/Eratostena_siets" title="Eratostena siets – Latvian" lang="lv" hreflang="lv" data-title="Eratostena siets" data-language-autonym="Latviešu" data-language-local-name="Latvian" class="interlanguage-link-target"><span>Latviešu</span></a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Eratosteno_r%C4%97tis" title="Eratosteno rėtis – Lithuanian" lang="lt" hreflang="lt" data-title="Eratosteno rėtis" data-language-autonym="Lietuvių" data-language-local-name="Lithuanian" class="interlanguage-link-target"><span>Lietuvių</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Cribi_de_Eratosten" title="Cribi de Eratosten – Lombard" lang="lmo" hreflang="lmo" data-title="Cribi de Eratosten" data-language-autonym="Lombard" data-language-local-name="Lombard" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Eratoszthen%C3%A9sz_szit%C3%A1ja" title="Eratoszthenész szitája – Hungarian" lang="hu" hreflang="hu" data-title="Eratoszthenész szitája" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-mk mw-list-item"><a href="https://mk.wikipedia.org/wiki/%D0%95%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%82%D0%B5%D0%BD%D0%BE%D0%B2%D0%BE_%D1%81%D0%B8%D1%82%D0%BE" title="Ератостеново сито – Macedonian" lang="mk" hreflang="mk" data-title="Ератостеново сито" data-language-autonym="Македонски" data-language-local-name="Macedonian" class="interlanguage-link-target"><span>Македонски</span></a></li><li class="interlanguage-link interwiki-mzn mw-list-item"><a href="https://mzn.wikipedia.org/wiki/%D8%A7%D8%B1%D8%A7%D8%AA%D9%88%D8%B3%D8%AA%D9%86_%D8%BA%D8%B1%D8%A8%D8%A7%D9%84" title="اراتوستن غربال – Mazanderani" lang="mzn" hreflang="mzn" data-title="اراتوستن غربال" data-language-autonym="مازِرونی" data-language-local-name="Mazanderani" class="interlanguage-link-target"><span>مازِرونی</span></a></li><li class="interlanguage-link interwiki-ms mw-list-item"><a href="https://ms.wikipedia.org/wiki/Saringan_Eratosthenes" title="Saringan Eratosthenes – Malay" lang="ms" hreflang="ms" data-title="Saringan Eratosthenes" data-language-autonym="Bahasa Melayu" data-language-local-name="Malay" class="interlanguage-link-target"><span>Bahasa Melayu</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Zeef_van_Eratosthenes" title="Zeef van Eratosthenes – Dutch" lang="nl" hreflang="nl" data-title="Zeef van Eratosthenes" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9" title="エラトステネスの篩 – Japanese" lang="ja" hreflang="ja" data-title="エラトステネスの篩" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-nap mw-list-item"><a href="https://nap.wikipedia.org/wiki/Cilivere_r%27Eratosten" title="Cilivere r'Eratosten – Neapolitan" lang="nap" hreflang="nap" data-title="Cilivere r'Eratosten" data-language-autonym="Napulitano" data-language-local-name="Neapolitan" class="interlanguage-link-target"><span>Napulitano</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Eratosthenes%E2%80%99_sil" title="Eratosthenes’ sil – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Eratosthenes’ sil" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-oc mw-list-item"><a href="https://oc.wikipedia.org/wiki/Criv%C3%A8l_d%27Eratostenes" title="Crivèl d'Eratostenes – Occitan" lang="oc" hreflang="oc" data-title="Crivèl d'Eratostenes" data-language-autonym="Occitan" data-language-local-name="Occitan" class="interlanguage-link-target"><span>Occitan</span></a></li><li class="interlanguage-link interwiki-uz mw-list-item"><a href="https://uz.wikipedia.org/wiki/Eratosfen_elagi" title="Eratosfen elagi – Uzbek" lang="uz" hreflang="uz" data-title="Eratosfen elagi" data-language-autonym="Oʻzbekcha / ўзбекча" data-language-local-name="Uzbek" class="interlanguage-link-target"><span>Oʻzbekcha / ўзбекча</span></a></li><li class="interlanguage-link interwiki-pms mw-list-item"><a href="https://pms.wikipedia.org/wiki/Siass_d%27Erat%C3%B2stene" title="Siass d'Eratòstene – Piedmontese" lang="pms" hreflang="pms" data-title="Siass d'Eratòstene" data-language-autonym="Piemontèis" data-language-local-name="Piedmontese" class="interlanguage-link-target"><span>Piemontèis</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Sito_Eratostenesa" title="Sito Eratostenesa – Polish" lang="pl" hreflang="pl" data-title="Sito Eratostenesa" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes" title="Crivo de Eratóstenes – Portuguese" lang="pt" hreflang="pt" data-title="Crivo de Eratóstenes" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Ciurul_lui_Eratostene" title="Ciurul lui Eratostene – Romanian" lang="ro" hreflang="ro" data-title="Ciurul lui Eratostene" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0" title="Решето Эратосфена – Russian" lang="ru" hreflang="ru" data-title="Решето Эратосфена" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sq mw-list-item"><a href="https://sq.wikipedia.org/wiki/Sita_e_Eratostenit" title="Sita e Eratostenit – Albanian" lang="sq" hreflang="sq" data-title="Sita e Eratostenit" data-language-autonym="Shqip" data-language-local-name="Albanian" class="interlanguage-link-target"><span>Shqip</span></a></li><li class="interlanguage-link interwiki-scn mw-list-item"><a href="https://scn.wikipedia.org/wiki/Criveddu_d%27Erat%C3%B2stini" title="Criveddu d'Eratòstini – Sicilian" lang="scn" hreflang="scn" data-title="Criveddu d'Eratòstini" data-language-autonym="Sicilianu" data-language-local-name="Sicilian" class="interlanguage-link-target"><span>Sicilianu</span></a></li><li class="interlanguage-link interwiki-si mw-list-item"><a href="https://si.wikipedia.org/wiki/%E0%B6%91%E0%B6%BB%E0%B6%A7%E0%B7%9C%E0%B7%83%E0%B7%8A%E0%B6%AD%E0%B6%B1%E0%B7%93%E0%B7%83%E0%B7%8A%E0%B6%9C%E0%B7%9A_%E0%B6%B4%E0%B7%99%E0%B6%B1%E0%B7%9A%E0%B6%BB%E0%B6%BA" title="එරටොස්තනීස්ගේ පෙනේරය – Sinhala" lang="si" hreflang="si" data-title="එරටොස්තනීස්ගේ පෙනේරය" data-language-autonym="සිංහල" data-language-local-name="Sinhala" class="interlanguage-link-target"><span>සිංහල</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Sieve_of_Eratosthenes" title="Sieve of Eratosthenes – Simple English" lang="en-simple" hreflang="en-simple" data-title="Sieve of Eratosthenes" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Eratostenovo_sito" title="Eratostenovo sito – Slovak" lang="sk" hreflang="sk" data-title="Eratostenovo sito" data-language-autonym="Slovenčina" data-language-local-name="Slovak" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/Eratostenovo_sito" title="Eratostenovo sito – Slovenian" lang="sl" hreflang="sl" data-title="Eratostenovo sito" data-language-autonym="Slovenščina" data-language-local-name="Slovenian" class="interlanguage-link-target"><span>Slovenščina</span></a></li><li class="interlanguage-link interwiki-ckb mw-list-item"><a href="https://ckb.wikipedia.org/wiki/%D8%A8%DB%8E%DA%98%D9%86%DA%AF%DB%8C_%D8%A6%DB%95%D8%B1%D8%A7%D8%AA%DB%86%D8%B3%D8%AA%DB%8E%D9%86" title="بێژنگی ئەراتۆستێن – Central Kurdish" lang="ckb" hreflang="ckb" data-title="بێژنگی ئەراتۆستێن" data-language-autonym="کوردی" data-language-local-name="Central Kurdish" class="interlanguage-link-target"><span>کوردی</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%95%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%82%D0%B5%D0%BD%D0%BE%D0%B2%D0%BE_%D1%81%D0%B8%D1%82%D0%BE" title="Ератостеново сито – Serbian" lang="sr" hreflang="sr" data-title="Ератостеново сито" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Eratostenovo_sito" title="Eratostenovo sito – Serbo-Croatian" lang="sh" hreflang="sh" data-title="Eratostenovo sito" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Eratostheneen_seula" title="Eratostheneen seula – Finnish" lang="fi" hreflang="fi" data-title="Eratostheneen seula" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Eratosthenes_s%C3%A5ll" title="Eratosthenes såll – Swedish" lang="sv" hreflang="sv" data-title="Eratosthenes såll" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%95%E0%B8%B0%E0%B9%81%E0%B8%81%E0%B8%A3%E0%B8%87%E0%B8%82%E0%B8%AD%E0%B8%87%E0%B9%80%E0%B8%AD%E0%B8%A3%E0%B8%B2%E0%B8%97%E0%B8%AD%E0%B8%AA%E0%B9%80%E0%B8%97%E0%B8%99%E0%B8%B5%E0%B8%AA" title="ตะแกรงของเอราทอสเทนีส – Thai" lang="th" hreflang="th" data-title="ตะแกรงของเอราทอสเทนีส" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Eratosten_kalburu" title="Eratosten kalburu – Turkish" lang="tr" hreflang="tr" data-title="Eratosten kalburu" data-language-autonym="Türkçe" data-language-local-name="Turkish" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%95%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0" title="Решето Ератосфена – Ukrainian" lang="uk" hreflang="uk" data-title="Решето Ератосфена" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes" title="Sàng Eratosthenes – Vietnamese" lang="vi" hreflang="vi" data-title="Sàng Eratosthenes" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E6%84%9B%E6%B0%8F%E7%AF%A9" title="愛氏篩 – Cantonese" lang="yue" hreflang="yue" data-title="愛氏篩" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95" title="埃拉托斯特尼筛法 – Chinese" lang="zh" hreflang="zh" data-title="埃拉托斯特尼筛法" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q177898#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit 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_Eratosthenes" 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_Eratosthenes" 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_Eratosthenes"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Sieve_of_Eratosthenes&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_Eratosthenes&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_Eratosthenes"><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_Eratosthenes&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_Eratosthenes&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_Eratosthenes" 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_Eratosthenes" 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="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Sieve_of_Eratosthenes&oldid=1273069038" 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_Eratosthenes&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_Eratosthenes&id=1273069038&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_Eratosthenes"><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_Eratosthenes"><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_Eratosthenes&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_Eratosthenes&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 class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Sieve_of_Eratosthenes" hreflang="en"><span>Wikimedia Commons</span></a></li><li class="wb-otherproject-link wb-otherproject-wikifunctions mw-list-item"><a href="https://www.wikifunctions.org/wiki/Z21187" hreflang="en"><span>Wikifunctions</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q177898" 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">Ancient algorithm for generating prime numbers</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">For the sculpture, see <a href="/wiki/The_Sieve_of_Eratosthenes_(sculpture)" title="The Sieve of Eratosthenes (sculpture)">The Sieve of Eratosthenes (sculpture)</a>.</div> <figure class="mw-halign-right" typeof="mw:File/Frame"><a href="/wiki/File:Animation_Sieve_of_Eratosth.gif" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/9/94/Animation_Sieve_of_Eratosth.gif" decoding="async" width="445" height="369" class="mw-file-element" data-file-width="445" data-file-height="369" /></a><figcaption>Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square).</figcaption></figure> <p>In <a href="/wiki/Mathematics" title="Mathematics">mathematics</a>, the <b>sieve of Eratosthenes</b> is an ancient <a href="/wiki/Algorithm" title="Algorithm">algorithm</a> for finding all <a href="/wiki/Prime_number" title="Prime number">prime numbers</a> up to any given limit. </p><p>It does so by iteratively marking as <a href="/wiki/Composite_number" title="Composite number">composite</a> (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with <a href="/wiki/Arithmetic_progression" title="Arithmetic progression">constant difference between them</a> that is equal to that prime.<sup id="cite_ref-horsley_1-0" class="reference"><a href="#cite_note-horsley-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> This is the sieve's key distinction from using <a href="/wiki/Trial_division" title="Trial division">trial division</a> to sequentially test each candidate number for divisibility by each prime.<sup id="cite_ref-ONeill_2-0" class="reference"><a href="#cite_note-ONeill-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes. </p><p>The earliest known reference to the sieve (<a href="/wiki/Ancient_Greek_language" class="mw-redirect" title="Ancient Greek language">Ancient Greek</a>: <span lang="grc">κόσκινον Ἐρατοσθένους</span>, <i>kóskinon Eratosthénous</i>) is in <a href="/wiki/Nicomachus" title="Nicomachus">Nicomachus of Gerasa</a>'s <i><a href="/wiki/Introduction_to_Arithmetic" class="mw-redirect" title="Introduction to Arithmetic">Introduction to Arithmetic</a></i>,<sup id="cite_ref-nicomachus_3-0" class="reference"><a href="#cite_note-nicomachus-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> an early 2nd century CE book which attributes it to <a href="/wiki/Eratosthenes" title="Eratosthenes">Eratosthenes of Cyrene</a>, a 3rd century BCE <a href="/wiki/Greek_mathematics" title="Greek mathematics">Greek mathematician</a>, though describing the sieving by odd numbers instead of by primes.<sup id="cite_ref-nicomachus1926_4-0" class="reference"><a href="#cite_note-nicomachus1926-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p><p>One of a number of <a href="/wiki/Generating_primes#Prime_sieves" class="mw-redirect" title="Generating primes">prime number sieves</a>, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in <a href="/wiki/Arithmetic_progression" title="Arithmetic progression">arithmetic progressions</a>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<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_Eratosthenes&action=edit&section=1" title="Edit section: Overview"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1224211176">.mw-parser-output .quotebox{background-color:#F9F9F9;border:1px solid #aaa;box-sizing:border-box;padding:10px;font-size:88%;max-width:100%}.mw-parser-output .quotebox.floatleft{margin:.5em 1.4em .8em 0}.mw-parser-output .quotebox.floatright{margin:.5em 0 .8em 1.4em}.mw-parser-output .quotebox.centered{overflow:hidden;position:relative;margin:.5em auto .8em auto}.mw-parser-output .quotebox.floatleft span,.mw-parser-output .quotebox.floatright span{font-style:inherit}.mw-parser-output .quotebox>blockquote{margin:0;padding:0;border-left:0;font-family:inherit;font-size:inherit}.mw-parser-output .quotebox-title{text-align:center;font-size:110%;font-weight:bold}.mw-parser-output .quotebox-quote>:first-child{margin-top:0}.mw-parser-output .quotebox-quote:last-child>:last-child{margin-bottom:0}.mw-parser-output .quotebox-quote.quoted:before{font-family:"Times New Roman",serif;font-weight:bold;font-size:large;color:gray;content:" “ ";vertical-align:-45%;line-height:0}.mw-parser-output .quotebox-quote.quoted:after{font-family:"Times New Roman",serif;font-weight:bold;font-size:large;color:gray;content:" ” ";line-height:0}.mw-parser-output .quotebox .left-aligned{text-align:left}.mw-parser-output .quotebox .right-aligned{text-align:right}.mw-parser-output .quotebox .center-aligned{text-align:center}.mw-parser-output .quotebox .quote-title,.mw-parser-output .quotebox .quotebox-quote{display:block}.mw-parser-output .quotebox cite{display:block;font-style:normal}@media screen and (max-width:640px){.mw-parser-output .quotebox{width:100%!important;margin:0 0 .8em!important;float:none!important}}</style><div class="quotebox pullquote floatright" style="; font-size: 105%;"> <blockquote class="quotebox-quote left-aligned" style=""> <p><i>Sift the Two's and Sift the Three's:</i><br /><i>The Sieve of Eratosthenes.</i><br /><i>When the multiples sublime,</i><br /><i>The numbers that remain are Prime.</i> </p> </blockquote> <div style="padding-bottom: 0; padding-top: 0.5em"><cite class="center-aligned" style="">Anonymous<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup></cite></div> </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 exactly two distinct natural number <a href="/wiki/Divisor" title="Divisor">divisors</a>: the number <a href="/wiki/1" title="1">1</a> and itself. </p><p>To find all the prime numbers less than or equal to a given integer <span class="texhtml mvar" style="font-style:italic;">n</span> by Eratosthenes' method: </p> <ol><li>Create a list of consecutive integers from 2 through <span class="texhtml mvar" style="font-style:italic;">n</span>: <span class="texhtml">(2, 3, 4, ..., <i>n</i>)</span>.</li> <li>Initially, let <span class="texhtml mvar" style="font-style:italic;">p</span> equal 2, the smallest prime number.</li> <li>Enumerate the multiples of <span class="texhtml mvar" style="font-style:italic;">p</span> by counting in increments of <span class="texhtml mvar" style="font-style:italic;">p</span> from <span class="texhtml">2<i>p</i></span> to <span class="texhtml mvar" style="font-style:italic;">n</span>, and mark them in the list (these will be <span class="texhtml">2<i>p</i>, 3<i>p</i>, 4<i>p</i>, ...</span>; the <span class="texhtml mvar" style="font-style:italic;">p</span> itself should not be marked).</li> <li>Find the smallest number in the list greater than <span class="texhtml mvar" style="font-style:italic;">p</span> that is not marked. If there was no such number, stop. Otherwise, let <span class="texhtml mvar" style="font-style:italic;">p</span> now equal this new number (which is the next prime), and repeat from step 3.</li> <li>When the algorithm terminates, the numbers remaining not marked in the list are all the primes below <span class="texhtml mvar" style="font-style:italic;">n</span>.</li></ol> <p>The main idea here is that every value given to <span class="texhtml mvar" style="font-style:italic;">p</span> will be prime, because if it were composite it would be marked as a multiple of some other, smaller prime. Note that some of the numbers may be marked more than once (e.g., 15 will be marked both for 3 and 5). </p><p>As a refinement, it is sufficient to mark the numbers in step 3 starting from <span class="texhtml"><i>p</i><sup>2</sup></span>, as all the smaller multiples of <span class="texhtml mvar" style="font-style:italic;">p</span> will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when <span class="texhtml"><i>p</i><sup>2</sup></span> is greater than <span class="texhtml mvar" style="font-style:italic;">n</span>.<sup id="cite_ref-horsley_1-1" class="reference"><a href="#cite_note-horsley-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>Another refinement is to initially list odd numbers only, <span class="texhtml">(3, 5, ..., <i>n</i>)</span>, and count in increments of <span class="texhtml">2<i>p</i></span> in step 3, thus marking only odd multiples of <span class="texhtml mvar" style="font-style:italic;">p</span>. This actually appears in the original algorithm.<sup id="cite_ref-horsley_1-2" class="reference"><a href="#cite_note-horsley-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-nicomachus1926_4-1" class="reference"><a href="#cite_note-nicomachus1926-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> This can be generalized with <a href="/wiki/Wheel_factorization" title="Wheel factorization">wheel factorization</a>, forming the initial list only from numbers <a href="/wiki/Coprime" class="mw-redirect" title="Coprime">coprime</a> with the first few primes and not just from odds (i.e., numbers coprime with 2), and counting in the correspondingly adjusted increments so that only such multiples of <span class="texhtml mvar" style="font-style:italic;">p</span> are generated that are coprime with those small primes, in the first place.<sup id="cite_ref-Runciman_7-0" class="reference"><a href="#cite_note-Runciman-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p> <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_Eratosthenes&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 30, proceed as follows. </p><p>First, generate a list of integers from 2 to 30: </p> <pre> 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 </pre> <p>The first number in the list is 2; cross out every 2nd number in the list after 2 by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list): </p> <pre> 2 3 <span style="color:gray"><s> 4 </s></span> 5 <span style="color:gray"><s> 6 </s></span> 7 <span style="color:gray"><s> 8 </s></span> 9 <span style="color:gray"><s>10</s></span> 11 <span style="color:gray"><s>12</s></span> 13 <span style="color:gray"><s>14</s></span> 15 <span style="color:gray"><s>16</s></span> 17 <span style="color:gray"><s>18</s></span> 19 <span style="color:gray"><s>20</s></span> 21 <span style="color:gray"><s>22</s></span> 23 <span style="color:gray"><s>24</s></span> 25 <span style="color:gray"><s>26</s></span> 27 <span style="color:gray"><s>28</s></span> 29 <span style="color:gray"><s>30</s></span> </pre> <p>The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list): </p> <pre> 2 3 <span style="color:gray"><s> 4 </s></span> 5 <span style="color:gray"><s> 6 </s></span> 7 <span style="color:gray"><s> 8 </s></span><span style="color:gray"><s> 9 </s></span><span style="color:gray"><s>10</s></span> 11 <span style="color:gray"><s>12</s></span> 13 <span style="color:gray"><s>14 </s></span><span style="color:gray"><s>15 </s></span><span style="color:gray"><s>16</s></span> 17 <span style="color:gray"><s>18</s></span> 19 <span style="color:gray"><s>20 </s></span><span style="color:gray"><s>21 </s></span><span style="color:gray"><s>22</s></span> 23 <span style="color:gray"><s>24</s></span> 25 <span style="color:gray"><s>26 </s></span><span style="color:gray"><s>27 </s></span><span style="color:gray"><s>28</s></span> 29 <span style="color:gray"><s>30</s></span> </pre> <p>The next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after 5 by counting up from 5 in increments of 5 (i.e. all the multiples of 5): </p> <pre> 2 3 <span style="color:gray"><s> 4 </s></span> 5 <span style="color:gray"><s> 6 </s></span> 7 <span style="color:gray"><s> 8 </s></span><span style="color:gray"><s> 9 </s></span><span style="color:gray"><s>10</s></span> 11 <span style="color:gray"><s>12</s></span> 13 <span style="color:gray"><s>14 </s></span><span style="color:gray"><s>15 </s></span><span style="color:gray"><s>16</s></span> 17 <span style="color:gray"><s>18</s></span> 19 <span style="color:gray"><s>20 </s></span><span style="color:gray"><s>21 </s></span><span style="color:gray"><s>22</s></span> 23 <span style="color:gray"><s>24 </s></span><span style="color:gray"><s>25 </s></span><span style="color:gray"><s>26 </s></span><span style="color:gray"><s>27 </s></span><span style="color:gray"><s>28</s></span> 29 <span style="color:gray"><s>30</s></span> </pre> <p>The next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7th number in the list after 7, but they are all already crossed out at this point, as these numbers (14, 21, 28) are also multiples of smaller primes because 7 × 7 is greater than 30. The numbers not crossed out at this point in the list are all the prime numbers below 30: </p> <pre> 2 3 5 7 11 13 17 19 23 29 </pre> <div class="mw-heading mw-heading2"><h2 id="Algorithm_and_variants">Algorithm and variants</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Eratosthenes&action=edit&section=3" title="Edit section: Algorithm and variants"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Pseudocode">Pseudocode</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Eratosthenes&action=edit&section=4" title="Edit section: Pseudocode"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The sieve of Eratosthenes can be expressed in <a href="/wiki/Pseudocode" title="Pseudocode">pseudocode</a>, as follows:<sup id="cite_ref-sedgewick_8-0" class="reference"><a href="#cite_note-sedgewick-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-intro_9-0" class="reference"><a href="#cite_note-intro-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p> <pre><b>algorithm</b> Sieve of Eratosthenes <b>is</b> <b>input</b>: an integer <i>n</i> > 1. <b>output</b>: all prime numbers from 2 through <i>n</i>. <b>let</b> <i>A</i> be an <b>array of <a href="/wiki/Boolean_data_type" title="Boolean data type">Boolean</a></b> values, indexed by <b>integer</b>s 2 to <i>n</i>, initially all <b>set</b> to <b>true</b>. <b>for</b> <i>i</i> = 2, 3, 4, ..., not exceeding <span class="texhtml"><i><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;">n</span></span></i></span> <b>do</b> <b>if</b> <i>A</i>[<i>i</i>] <b>is</b> <b>true</b> <b>for</b> <i>j</i> = <i>i</i><sup>2</sup>, <i>i</i><sup>2</sup>+<i>i</i>, <i>i</i><sup>2</sup>+2<i>i</i>, <i>i</i><sup>2</sup>+3<i>i</i>, ..., not exceeding <i>n</i> <b>do</b> <b>set</b> <i>A</i>[<i>j</i>] := <b>false</b> <b>return</b> all <i>i</i> such that <i>A</i>[<i>i</i>] <b>is</b> <b>true</b>. </pre> <p>This algorithm produces all primes not greater than <span class="texhtml mvar" style="font-style:italic;">n</span>. It includes a common optimization, which is to start enumerating the multiples of each prime <span class="texhtml mvar" style="font-style:italic;">i</span> from <span class="texhtml"><i>i</i><sup>2</sup></span>. The <a href="/wiki/Time_complexity" title="Time complexity">time complexity</a> of this algorithm is <span class="texhtml"><i>O</i>(<i>n</i> log log <i>n</i>)</span>,<sup id="cite_ref-intro_9-1" class="reference"><a href="#cite_note-intro-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> provided the array update is an <span class="texhtml"><i>O</i>(1)</span> operation, as is usually the case. </p> <div class="mw-heading mw-heading3"><h3 id="Segmented_sieve">Segmented sieve</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Eratosthenes&action=edit&section=5" title="Edit section: Segmented sieve"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>As Sorenson notes, the problem with the sieve of Eratosthenes is not the number of operations it performs but rather its memory requirements.<sup id="cite_ref-intro_9-2" class="reference"><a href="#cite_note-intro-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> For large <span class="texhtml mvar" style="font-style:italic;">n</span>, the range of primes may not fit in memory; worse, even for moderate <span class="texhtml mvar" style="font-style:italic;">n</span>, its <a href="/wiki/CPU_cache" title="CPU cache">cache</a> use is highly suboptimal. The algorithm walks through the entire array <span class="texhtml mvar" style="font-style:italic;">A</span>, exhibiting almost no <a href="/wiki/Locality_of_reference" title="Locality of reference">locality of reference</a>. </p><p>A solution to these problems is offered by <i>segmented</i> sieves, where only portions of the range are sieved at a time.<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> These have been known since the 1970s, and work as follows:<sup id="cite_ref-intro_9-3" class="reference"><a href="#cite_note-intro-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><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> </p> <ol><li>Divide the range 2 through <span class="texhtml mvar" style="font-style:italic;">n</span> into segments of some size <span class="texhtml">Δ ≥ <span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span></span>.</li> <li>Find the primes in the first (i.e. the lowest) segment, using the regular sieve.</li> <li>For each of the following segments, in increasing order, with <span class="texhtml mvar" style="font-style:italic;">m</span> being the segment's topmost value, find the primes in it as follows: <ol><li>Set up a Boolean array of size <span class="texhtml">Δ</span>.</li> <li>Mark as non-prime the positions in the array corresponding to the multiples of each prime <span class="texhtml"><i>p</i> ≤ <span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>m</i></span></span></span> found so far, by enumerating its multiples in steps of <span class="texhtml"><i>p</i></span> starting from the lowest multiple of <span class="texhtml"><i>p</i></span> between <span class="texhtml"><span class="texhtml mvar" style="font-style:italic;">m</span> - Δ</span> and <span class="texhtml mvar" style="font-style:italic;">m</span>.</li> <li>The remaining non-marked positions in the array correspond to the primes in the segment. It is not necessary to mark any multiples of <i>these</i> primes, because all of these primes are larger than <span class="texhtml"><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>m</i></span></span></span>, as for <span class="texhtml"><i>k</i> ≥ 1</span>, one has <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\Delta +1)^{2}>(k+1)\Delta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>k</mi> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>></mo> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mi mathvariant="normal">Δ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (k\Delta +1)^{2}>(k+1)\Delta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7af49e3d46df090309bcb77687caae23d321b794" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.071ex; height:3.176ex;" alt="{\displaystyle (k\Delta +1)^{2}>(k+1)\Delta }"></span>.</li></ol></li></ol> <p>If <span class="texhtml">Δ</span> is chosen to be <span class="texhtml"><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span></span>, the space complexity of the algorithm is <span class="texhtml"><i>O</i>(<span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span>)</span>, while the time complexity is the same as that of the regular sieve.<sup id="cite_ref-intro_9-4" class="reference"><a href="#cite_note-intro-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p><p>For ranges with upper limit <span class="texhtml"><i>n</i></span> so large that the sieving primes below <span class="texhtml"><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span></span> as required by the page segmented sieve of Eratosthenes cannot fit in memory, a slower but much more space-efficient sieve like the pseudosquares prime sieve, developed by Jonathan P. Sorenson, can be used instead.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Incremental_sieve">Incremental sieve</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Eratosthenes&action=edit&section=6" title="Edit section: Incremental sieve"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>An incremental formulation of the sieve<sup id="cite_ref-ONeill_2-1" class="reference"><a href="#cite_note-ONeill-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> generates primes indefinitely (i.e., without an upper bound) by interleaving the generation of primes with the generation of their multiples (so that primes can be found in gaps between the multiples), where the multiples of each prime <span class="texhtml mvar" style="font-style:italic;">p</span> are generated directly by counting up from the square of the prime in increments of <span class="texhtml mvar" style="font-style:italic;">p</span> (or <span class="texhtml">2<i>p</i></span> for odd primes). The generation must be initiated only when the prime's square is reached, to avoid adverse effects on efficiency. It can be expressed symbolically under the <a href="/wiki/Dataflow_programming" title="Dataflow programming">dataflow</a> paradigm as </p> <pre><i>primes</i> = [<i>2</i>, <i>3</i>, ...] \ [[<i>p</i>², <i>p</i>²+<i>p</i>, ...] for <i>p</i> in <i>primes</i>], </pre> <p>using <a href="/wiki/List_comprehension" title="List comprehension">list comprehension</a> notation with <code>\</code> denoting <a href="/wiki/Complement_(set_theory)#Relative_complement" title="Complement (set theory)">set subtraction</a> of <a href="/wiki/Arithmetic_progressions" class="mw-redirect" title="Arithmetic progressions">arithmetic progressions</a> of numbers. </p><p>Primes can also be produced by iteratively sieving out the composites through <a href="/wiki/Trial_division" title="Trial division">divisibility testing</a> by sequential primes, one prime at a time. It is not the sieve of Eratosthenes but is often confused with it, even though the sieve of Eratosthenes directly generates the composites instead of testing for them. Trial division has worse theoretical <a href="/wiki/Analysis_of_algorithms" title="Analysis of algorithms">complexity</a> than that of the sieve of Eratosthenes in generating ranges of primes.<sup id="cite_ref-ONeill_2-2" class="reference"><a href="#cite_note-ONeill-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p><p>When testing each prime, the <i>optimal</i> trial division algorithm uses all prime numbers not exceeding its square root, whereas the sieve of Eratosthenes produces each composite from its prime factors only, and gets the primes "for free", between the composites. The widely known 1975 <a href="/wiki/Functional_programming" title="Functional programming">functional</a> sieve code by <a href="/wiki/David_Turner_(computer_scientist)" title="David Turner (computer scientist)">David Turner</a><sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> is often presented as an example of the sieve of Eratosthenes<sup id="cite_ref-Runciman_7-1" class="reference"><a href="#cite_note-Runciman-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> but is actually a sub-optimal trial division sieve.<sup id="cite_ref-ONeill_2-3" class="reference"><a href="#cite_note-ONeill-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Algorithmic_complexity">Algorithmic complexity</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Eratosthenes&action=edit&section=7" title="Edit section: Algorithmic complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The sieve of Eratosthenes is a popular way to benchmark computer performance.<sup id="cite_ref-peng1985fall_14-0" class="reference"><a href="#cite_note-peng1985fall-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> The <a href="/wiki/Time_complexity" title="Time complexity">time complexity</a> of calculating all primes below <span class="texhtml mvar" style="font-style:italic;">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="texhtml"><i>O</i>(<i>n</i> log log <i>n</i>)</span> operations, a direct consequence of the fact that the <a href="/wiki/Prime_harmonic_series" class="mw-redirect" title="Prime harmonic series">prime harmonic series</a> asymptotically approaches <span class="texhtml">log log <i>n</i></span>. It has an exponential time complexity with regard to length of the input, though, which makes it a <a href="/wiki/Pseudo-polynomial_time" title="Pseudo-polynomial time">pseudo-polynomial</a> algorithm. The basic algorithm requires <span class="texhtml"><i>O</i>(<i>n</i>)</span> of memory. </p><p>The <a href="/wiki/Bit_complexity" class="mw-redirect" title="Bit complexity">bit complexity</a> of the algorithm is <span class="texhtml"><i>O</i><big>(</big><i>n</i> (log <i>n</i>) (log log <i>n</i>)<big>)</big></span> bit operations with a memory requirement of <span class="texhtml"><i>O</i>(<i>n</i>)</span>.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p><p>The normally implemented page segmented version has the same operational complexity of <span class="texhtml"><i>O</i>(<i>n</i> log log <i>n</i>)</span> as the non-segmented version but reduces the space requirements to the very minimal size of the segment page plus the memory required to store the base primes less than the square root of the range used to cull composites from successive page segments of size <span class="texhtml"><i>O</i><big><big>(</big></big><style data-mw-deduplicate="TemplateStyles:r1214402035">.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}</style><span class="sfrac">⁠<span class="tion"><span class="num"><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span></span><span class="sr-only">/</span><span class="den">log <i>n</i></span></span>⁠</span><big><big>)</big></big></span>. </p><p>A special (rarely, if ever, implemented) segmented version of the sieve of Eratosthenes, with basic optimizations, uses <span class="texhtml"><i>O</i>(<i>n</i>)</span> operations and <span class="texhtml"><i>O</i><big><big>(</big></big><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1214402035"><span class="sfrac">⁠<span class="tion"><span class="num">log log <i>n</i></span><span class="sr-only">/</span><span class="den">log <i>n</i></span></span>⁠</span><big><big>)</big></big></span> bits of memory.<sup id="cite_ref-Pritchard1_16-0" class="reference"><a href="#cite_note-Pritchard1-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Pritchard2_17-0" class="reference"><a href="#cite_note-Pritchard2-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Pritchard3_18-0" class="reference"><a href="#cite_note-Pritchard3-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> </p><p>Using <a href="/wiki/Big_O_notation" title="Big O notation">big O notation</a> ignores constant factors and offsets that may be very significant for practical ranges: The sieve of Eratosthenes variation known as the Pritchard wheel sieve<sup id="cite_ref-Pritchard1_16-1" class="reference"><a href="#cite_note-Pritchard1-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Pritchard2_17-1" class="reference"><a href="#cite_note-Pritchard2-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Pritchard3_18-1" class="reference"><a href="#cite_note-Pritchard3-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> has an <span class="texhtml"><i>O</i>(<i>n</i>)</span> performance, but its basic implementation requires either a "one large array" algorithm which limits its usable range to the amount of available memory else it needs to be page segmented to reduce memory use. When implemented with page segmentation in order to save memory, the basic algorithm still requires about <span class="texhtml"><i>O</i><big><big>(</big></big><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1214402035"><span class="sfrac">⁠<span class="tion"><span class="num"><i>n</i></span><span class="sr-only">/</span><span class="den">log <i>n</i></span></span>⁠</span><big><big>)</big></big></span> bits of memory (much more than the requirement of the basic page segmented sieve of Eratosthenes using <span class="texhtml"><i>O</i><big><big>(</big></big><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1214402035"><span class="sfrac">⁠<span class="tion"><span class="num"><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span></span><span class="sr-only">/</span><span class="den">log <i>n</i></span></span>⁠</span><big><big>)</big></big></span> bits of memory). Pritchard's work reduced the memory requirement at the cost of a large constant factor. Although the resulting wheel sieve has <span class="texhtml"><i>O</i>(<i>n</i>)</span> performance and an acceptable memory requirement, it is not faster than a reasonably Wheel Factorized basic sieve of Eratosthenes for practical sieving ranges. </p> <div class="mw-heading mw-heading2"><h2 id="Euler's_sieve"><span id="Euler.27s_sieve"></span>Euler's sieve</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Eratosthenes&action=edit&section=8" title="Edit section: Euler's sieve"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Euler's <a href="/wiki/Proof_of_the_Euler_product_formula_for_the_Riemann_zeta_function#Proof_of_the_Euler_product_formula" title="Proof of the Euler product formula for the Riemann zeta function">proof of the zeta product formula</a> contains a version of the sieve of Eratosthenes in which each composite number is eliminated exactly once.<sup id="cite_ref-intro_9-5" class="reference"><a href="#cite_note-intro-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> The same sieve was rediscovered and observed to take <a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear time</a> by <a href="#CITEREFGriesMisra1978">Gries & Misra (1978)</a>.<sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> It, too, starts with a <a href="/wiki/List_(computing)" class="mw-redirect" title="List (computing)">list</a> of numbers from 2 to <span class="texhtml mvar" style="font-style:italic;">n</span> in order. On each step the first element is identified as the next prime, is multiplied with each element of the list (thus starting with itself), and the results are marked in the list for subsequent deletion. The initial element and the marked elements are then removed from the working sequence, and the process is repeated: </p> <div style="font-size:85%;"> <pre> [2] (3) 5 7 <u>9</u> 11 13 <u>15</u> 17 19 <u>21</u> 23 25 <u>27</u> 29 31 <u>33</u> 35 37 <u>39</u> 41 43 <u>45</u> 47 49 <u>51</u> 53 55 <u>57</u> 59 61 <u>63</u> 65 67 <u>69</u> 71 73 <u>75</u> 77 79 ...  [3] (5) 7 11 13 17 19 23 <u>25</u> 29 31 <u>35</u> 37 41 43 47 49 53 <u>55</u> 59 61 <u>65</u> 67 71 73 77 79 ...  [4] (7) 11 13 17 19 23 29 31 37 41 43 47 <u>49</u> 53 59 61 67 71 73 <u>77</u> 79 ...  [5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ...  [...] </pre> </div> <p>Here the example is shown starting from odds, after the first step of the algorithm. Thus, on the <span class="texhtml mvar" style="font-style:italic;">k</span>th step all the remaining multiples of the <span class="texhtml mvar" style="font-style:italic;">k</span>th prime are removed from the list, which will thereafter contain only numbers coprime with the first <span class="texhtml mvar" style="font-style:italic;">k</span> primes (cf. <a href="/wiki/Wheel_factorization" title="Wheel factorization">wheel factorization</a>), so that the list will start with the next prime, and all the numbers in it below the square of its first element will be prime too. </p><p>Thus, when generating a bounded sequence of primes, when the next identified prime exceeds the square root of the upper limit, all the remaining numbers in the list are prime.<sup id="cite_ref-intro_9-6" class="reference"><a href="#cite_note-intro-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> In the example given above that is achieved on identifying 11 as next prime, giving a list of all primes less than or equal to 80. </p><p>Note that numbers that will be discarded by a step are still used while marking the multiples in that step, e.g., for the multiples of 3 it is <span class="nowrap">3 × 3 = 9</span>, <span class="nowrap">3 × 5 = 15</span>, <span class="nowrap">3 × 7 = 21</span>, <span class="nowrap">3 × <i><b>9</b></i> = 27</span>, ..., <span class="nowrap">3 × <i><b>15</b></i> = 45</span>, ..., so care must be taken dealing with this.<sup id="cite_ref-intro_9-7" class="reference"><a href="#cite_note-intro-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </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_Eratosthenes&action=edit&section=9" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Sieve_of_Pritchard" title="Sieve of Pritchard">Sieve of Pritchard</a></li> <li><a href="/wiki/Sieve_of_Atkin" title="Sieve of Atkin">Sieve of Atkin</a></li> <li><a href="/wiki/Sieve_of_Sundaram" title="Sieve of Sundaram">Sieve of Sundaram</a></li> <li><a href="/wiki/Sieve_theory" title="Sieve theory">Sieve theory</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_Eratosthenes&action=edit&section=10" 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-horsley-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-horsley_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-horsley_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-horsley_1-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text">Horsley, Rev. Samuel, F. R. S., "<i><span title="Greek-language text"><span lang="el">Κόσκινον Ερατοσθένους</span></span></i> or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/106053"><i>Philosophical Transactions</i> (1683–1775), Vol. 62. (1772), pp. 327–347</a>.</span> </li> <li id="cite_note-ONeill-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-ONeill_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-ONeill_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-ONeill_2-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-ONeill_2-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text">O'Neill, Melissa E., <a rel="nofollow" class="external text" href="http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf">"The Genuine Sieve of Eratosthenes"</a>, <i>Journal of Functional Programming</i>, published online by Cambridge University Press 9 October 2008 <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><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%2FS0956796808007004">10.1017/S0956796808007004</a>, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).</span> </li> <li id="cite_note-nicomachus-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-nicomachus_3-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHoche1866" class="citation cs2"><a href="/wiki/Richard_Hoche" title="Richard Hoche">Hoche, Richard</a>, ed. (1866), <a rel="nofollow" class="external text" href="https://archive.org/stream/nicomachigerasen00nicouoft#page/30/mode/2up"><i>Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3</i></a>, Leipzig: B.G. Teubner, p. 30</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Nicomachi+Geraseni+Pythagorei+Introductionis+arithmeticae+libri+II%2C+chapter+XIII%2C+3&rft.place=Leipzig&rft.pages=30&rft.pub=B.G.+Teubner&rft.date=1866&rft_id=https%3A%2F%2Farchive.org%2Fstream%2Fnicomachigerasen00nicouoft%23page%2F30%2Fmode%2F2up&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Eratosthenes" class="Z3988"></span></span> </li> <li id="cite_note-nicomachus1926-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-nicomachus1926_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-nicomachus1926_4-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="CITEREFNicomachus_of_Gerasa1926" class="citation cs2">Nicomachus of Gerasa (1926), <i>Introduction to Arithmetic; translated into English by Martin Luther D'Ooge; with studies in Greek arithmetic by Frank Egleston Robbins and Louis Charles Karpinski, chapter XIII, 3</i>, New York: The Macmillan Company, p. 204</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Arithmetic%3B+translated+into+English+by+Martin+Luther+D%27Ooge%3B+with+studies+in+Greek+arithmetic+by+Frank+Egleston+Robbins+and+Louis+Charles+Karpinski%2C+chapter+XIII%2C+3&rft.place=New+York&rft.pages=204&rft.pub=The+Macmillan+Company&rft.date=1926&rft.au=Nicomachus+of+Gerasa&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Eratosthenes" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1967477"><i>Annals of Mathematics, Second Series</i> <b>10</b>:2 (1909), pp. 88–104</a>.</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">Clocksin, William F., Christopher S. Mellish, <i>Programming in Prolog</i>, 1984, p. 170. <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/3-540-11046-1" title="Special:BookSources/3-540-11046-1">3-540-11046-1</a>.</span> </li> <li id="cite_note-Runciman-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-Runciman_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Runciman_7-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="CITEREFRunciman1997" class="citation journal cs1">Runciman, Colin (1997). <a rel="nofollow" class="external text" href="http://eprints.whiterose.ac.uk/3784/1/runcimanc1.pdf">"Functional Pearl: Lazy wheel sieves and spirals of primes"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of Functional Programming</i>. <b>7</b> (2): <span class="nowrap">219–</span>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=Functional+Pearl%3A+Lazy+wheel+sieves+and+spirals+of+primes&rft.volume=7&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E219-%3C%2Fspan%3E225&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=Colin&rft_id=http%3A%2F%2Feprints.whiterose.ac.uk%2F3784%2F1%2Fruncimanc1.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Eratosthenes" class="Z3988"></span></span> </li> <li id="cite_note-sedgewick-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-sedgewick_8-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSedgewick1992" class="citation book cs1">Sedgewick, Robert (1992). <i>Algorithms in C++</i>. Addison-Wesley. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-51059-1" title="Special:BookSources/978-0-201-51059-1"><bdi>978-0-201-51059-1</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithms+in+C%2B%2B&rft.pub=Addison-Wesley&rft.date=1992&rft.isbn=978-0-201-51059-1&rft.aulast=Sedgewick&rft.aufirst=Robert&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Eratosthenes" class="Z3988"></span>, p. 16.</span> </li> <li id="cite_note-intro-9"><span class="mw-cite-backlink">^ <a href="#cite_ref-intro_9-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-intro_9-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-intro_9-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-intro_9-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-intro_9-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-intro_9-5"><sup><i><b>f</b></i></sup></a> <a href="#cite_ref-intro_9-6"><sup><i><b>g</b></i></sup></a> <a href="#cite_ref-intro_9-7"><sup><i><b>h</b></i></sup></a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://research.cs.wisc.edu/techreports/1990/TR909.pdf">Jonathan Sorenson, <i>An Introduction to Prime Number Sieves</i></a>, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2, 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).</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">Crandall & Pomerance, <i>Prime Numbers: A Computational Perspective</i>, second edition, Springer: 2005, pp. 121–24.</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="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): <span class="nowrap">121–</span>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=%3Cspan+class%3D%22nowrap%22%3E121-%3C%2Fspan%3E127&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+Eratosthenes" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text">J. Sorenson, <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/11792086_15">"The pseudosquares prime sieve"</a>, <i>Proceedings of the 7th International Symposium on Algorithmic Number Theory</i>. (ANTS-VII, 2006).</span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text">Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (<code class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><span class="nf">primes</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">sieve</span><span class="w"> </span><span class="p">[</span><span class="mi">2</span><span class="o">..</span><span class="p">];</span><span class="w"> </span><span class="n">sieve</span><span class="w"> </span><span class="p">(</span><span class="n">p</span><span class="kt">:</span><span class="n">nos</span><span class="p">)</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">p</span><span class="kt">:</span><span class="n">sieve</span><span class="w"> </span><span class="p">(</span><span class="n">remove</span><span class="w"> </span><span class="p">(</span><span class="n">multsof</span><span class="w"> </span><span class="n">p</span><span class="p">)</span><span class="w"> </span><span class="n">nos</span><span class="p">);</span><span class="w"> </span><span class="n">remove</span><span class="w"> </span><span class="n">m</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">filter</span><span class="w"> </span><span class="p">(</span><span class="n">not</span><span class="w"> </span><span class="o">.</span><span class="w"> </span><span class="n">m</span><span class="p">);</span><span class="w"> </span><span class="n">multsof</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">rem</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="n">p</span><span class="o">==</span><span class="mi">0</span></code>). But see also <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=811543&dl=ACM&coll=DL&CFID=663592028&CFTOKEN=36641676">Peter Henderson, Morris, James Jr., A Lazy Evaluator, 1976</a>, where we <a rel="nofollow" class="external text" href="http://www.seas.gwu.edu/~rhyspj/cs3221/lab8/henderson.pdf">find the following</a>, attributed to P. Quarendon: <code class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><span class="n">primeswrt</span><span class="p">[</span><span class="n">x</span><span class="p">;</span><span class="n">l</span><span class="p">]</span> <span class="o">=</span> <span class="k">if</span> <span class="n">car</span><span class="p">[</span><span class="n">l</span><span class="p">]</span> <span class="n">mod</span> <span class="n">x</span><span class="o">=</span><span class="mi">0</span> <span class="n">then</span> <span class="n">primeswrt</span><span class="p">[</span><span class="n">x</span><span class="p">;</span><span class="n">cdr</span><span class="p">[</span><span class="n">l</span><span class="p">]]</span> <span class="k">else</span> <span class="n">cons</span><span class="p">[</span><span class="n">car</span><span class="p">[</span><span class="n">l</span><span class="p">];</span><span class="n">primeswrt</span><span class="p">[</span><span class="n">x</span><span class="p">;</span><span class="n">cdr</span><span class="p">[</span><span class="n">l</span><span class="p">]]]</span> <span class="p">;</span> <span class="n">primes</span><span class="p">[</span><span class="n">l</span><span class="p">]</span> <span class="o">=</span> <span class="n">cons</span><span class="p">[</span><span class="n">car</span><span class="p">[</span><span class="n">l</span><span class="p">];</span><span class="n">primes</span><span class="p">[</span><span class="n">primeswrt</span><span class="p">[</span><span class="n">car</span><span class="p">[</span><span class="n">l</span><span class="p">];</span><span class="n">cdr</span><span class="p">[</span><span class="n">l</span><span class="p">]]]]</span> <span class="p">;</span> <span class="n">primes</span><span class="p">[</span><span class="n">integers</span><span class="p">[</span><span class="mi">2</span><span class="p">]]</span></code>; the priority is unclear.</span> </li> <li id="cite_note-peng1985fall-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-peng1985fall_14-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPeng,_T._A.1985" class="citation news cs1">Peng, T. A. (Fall 1985). <a rel="nofollow" class="external text" href="https://archive.org/stream/byte-magazine-1985-11/1985_11_BYTE_10-11_Inside_the_IBM_PCs#page/n245/mode/2up">"One Million Primes Through the Sieve"</a>. <i>BYTE</i>. pp. <span class="nowrap">243–</span>244<span class="reference-accessdate">. Retrieved <span class="nowrap">19 March</span> 2016</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=BYTE&rft.atitle=One+Million+Primes+Through+the+Sieve&rft.ssn=fall&rft.pages=%3Cspan+class%3D%22nowrap%22%3E243-%3C%2Fspan%3E244&rft.date=1985&rft.au=Peng%2C+T.+A.&rft_id=https%3A%2F%2Farchive.org%2Fstream%2Fbyte-magazine-1985-11%2F1985_11_BYTE_10-11_Inside_the_IBM_PCs%23page%2Fn245%2Fmode%2F2up&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Eratosthenes" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text">Pritchard, Paul, "Linear prime-number sieves: a family tree," <i>Sci. Comput. Programming</i> <b>9</b>:1 (1987), pp. 17–35.</span> </li> <li id="cite_note-Pritchard1-16"><span class="mw-cite-backlink">^ <a href="#cite_ref-Pritchard1_16-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Pritchard1_16-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Paul Pritchard, "A sublinear additive sieve for finding prime numbers", <i>Communications of the ACM</i> 24 (1981), 18–23. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=600730">600730</a></span> </li> <li id="cite_note-Pritchard2-17"><span class="mw-cite-backlink">^ <a href="#cite_ref-Pritchard2_17-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Pritchard2_17-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=685983">685983</a></span> </li> <li id="cite_note-Pritchard3-18"><span class="mw-cite-backlink">^ <a href="#cite_ref-Pritchard3_18-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Pritchard3_18-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Paul Pritchard, "Fast compact prime number sieves" (among others), <i>Journal of Algorithms</i> 4 (1983), 332–344. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=729229">729229</a></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGriesMisra1978" class="citation cs2"><a href="/wiki/David_Gries" title="David Gries">Gries, David</a>; Misra, Jayadev (December 1978), <a rel="nofollow" class="external text" href="https://ecommons.cornell.edu/bitstream/1813/6407/1/77-313.pdf">"A linear sieve algorithm for finding prime numbers"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a></i>, <b>21</b> (12): <span class="nowrap">999–</span>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=%3Cspan+class%3D%22nowrap%22%3E999-%3C%2Fspan%3E1003&rft.date=1978-12&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&rft_id=https%3A%2F%2Fecommons.cornell.edu%2Fbitstream%2F1813%2F6407%2F1%2F77-313.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASieve+of+Eratosthenes" class="Z3988"></span>.</span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Sieve_of_Eratosthenes&action=edit&section=11" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://primesieve.org/">primesieve – Very fast highly optimized C/C++ segmented Sieve of Eratosthenes</a></li> <li><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php/Eratosthenes,_sieve_of"><i>Eratosthenes, sieve of</i> at Encyclopaedia of Mathematics</a></li> <li><a rel="nofollow" class="external text" href="http://www.hbmeyer.de/eratosiv.htm">Interactive JavaScript Page</a></li> <li><a rel="nofollow" class="external text" href="http://demonstrations.wolfram.com/SieveOfEratosthenes/">Sieve of Eratosthenes</a> by George Beck, <a href="/wiki/Wolfram_Demonstrations_Project" title="Wolfram Demonstrations Project">Wolfram Demonstrations Project</a>.</li> <li><a rel="nofollow" class="external text" href="https://wiki.haskell.org/Prime_numbers#Sieve_of_Eratosthenes">Sieve of Eratosthenes in Haskell</a></li> <li><a rel="nofollow" class="external text" href="http://www.algolist.net/Algorithms/Number_theoretic_algorithms/Sieve_of_Eratosthenes">Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.</a></li> <li><a rel="nofollow" class="external text" href="http://zsmith.co/primes.html">A related sieve written in x86 assembly language</a></li> <li><a rel="nofollow" class="external text" href="https://sites.google.com/site/bbuhrow/home/cuda-sieve-of-eratosthenes">Fast optimized highly parallel CUDA segmented Sieve of Eratosthenes in C</a></li> <li><a rel="nofollow" class="external text" href="http://wiki.c2.com/?SieveOfEratosthenesInManyProgrammingLanguages">SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page</a></li> <li><a rel="nofollow" class="external text" href="http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html">The Art of Prime Sieving</a> Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained.</li></ul> <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_algorithms413" 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_algorithms413" 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 class="mw-selflink selflink">Sieve of Eratosthenes</a></li> <li><a href="/wiki/Sieve_of_Pritchard" title="Sieve of Pritchard">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?useformat=desktop&type=1x1&usesul3=0" 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_Eratosthenes&oldid=1273069038">https://en.wikipedia.org/w/index.php?title=Sieve_of_Eratosthenes&oldid=1273069038</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_containing_Greek-language_text" title="Category:Articles containing Greek-language text">Articles containing Greek-language text</a></li><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_containing_Ancient_Greek_(to_1453)-language_text" title="Category:Articles containing Ancient Greek (to 1453)-language text">Articles containing Ancient Greek (to 1453)-language text</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 31 January 2025, at 14:41<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_Eratosthenes&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" lang="en" 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"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div 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"> <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> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-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-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Sieve of Eratosthenes</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>62 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </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-b766959bd-n46nz","wgBackendResponseTime":135,"wgPageParseReport":{"limitreport":{"cputime":"0.595","walltime":"0.738","ppvisitednodes":{"value":4937,"limit":1000000},"postexpandincludesize":{"value":55857,"limit":2097152},"templateargumentsize":{"value":6939,"limit":2097152},"expansiondepth":{"value":16,"limit":100},"expensivefunctioncount":{"value":4,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":65854,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 633.668 1 -total"," 29.06% 184.162 1 Template:Reflist"," 19.56% 123.973 1 Template:Langx"," 11.31% 71.637 1 Template:Number_theoretic_algorithms"," 11.06% 70.098 1 Template:Short_description"," 11.06% 70.074 3 Template:Citation"," 10.50% 66.551 1 Template:Navbox"," 8.56% 54.261 38 Template:Math"," 6.87% 43.555 2 Template:Pagetype"," 5.92% 37.516 5 Template:Catalog_lookup_link"]},"scribunto":{"limitreport-timeusage":{"value":"0.343","limit":"10.000"},"limitreport-memusage":{"value":24611789,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFBaysHudson1977\"] = 1,\n [\"CITEREFGriesMisra1978\"] = 1,\n [\"CITEREFHoche1866\"] = 1,\n [\"CITEREFNicomachus_of_Gerasa1926\"] = 1,\n [\"CITEREFPeng,_T._A.1985\"] = 1,\n [\"CITEREFRunciman1997\"] = 1,\n [\"CITEREFSedgewick1992\"] = 1,\n}\ntemplate_list = table#1 {\n [\"Citation\"] = 3,\n [\"Cite book\"] = 1,\n [\"Cite journal\"] = 2,\n [\"Cite news\"] = 1,\n [\"DEFAULTSORT:Sieve Of Eratosthenes\"] = 1,\n [\"Doi\"] = 1,\n [\"For\"] = 1,\n [\"Gray\"] = 51,\n [\"Harvtxt\"] = 1,\n [\"Isbn\"] = 1,\n [\"Lang\"] = 1,\n [\"Langx\"] = 1,\n [\"MR\"] = 3,\n [\"Math\"] = 38,\n [\"Mvar\"] = 31,\n [\"Nowrap\"] = 5,\n [\"Number theoretic algorithms\"] = 1,\n [\"Quote box\"] = 1,\n [\"R\"] = 4,\n [\"Reflist\"] = 1,\n [\"Sfrac\"] = 4,\n [\"Short description\"] = 1,\n [\"Sqrt\"] = 10,\n}\narticle_whitelist = table#1 {\n}\nciteref_patterns = table#1 {\n}\n"},"cachereport":{"origin":"mw-web.codfw.main-b766959bd-g7l55","timestamp":"20250214040420","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Sieve of Eratosthenes","url":"https:\/\/en.wikipedia.org\/wiki\/Sieve_of_Eratosthenes","sameAs":"http:\/\/www.wikidata.org\/entity\/Q177898","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q177898","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":"2002-08-19T20:05:24Z","dateModified":"2025-01-31T14:41:38Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/9\/94\/Animation_Sieve_of_Eratosth.gif","headline":"ancient algorithm for generating prime numbers"}</script> </body> </html>