Ератосфен іркілісі: жай сандарды табу алгоритмі

Кіріспе

Бастапқы сандарды табудың ежелгі алгоритмі – мүсін. Математикада Эратостеннің сырғасы – кез келген берілген шекке дейін барлық бастапқы сандарды анықтаудың ежелгі алгоритмі. Ол 2-ден басталатын, әрбір бастапқы санның еселіктерін қайталап, құрама (яғни, бастапқы емес) деп белгілейді. Берілген бастапқы санның еселіктері сол бастапқы саннан басталатын сандар тізбегі түрінде құрылады, олардың арасындағы айырма сол бастапқы санға тең болады. Бұл, әрбір үміткер санды әрбір бастапқы санға бөлінетінін рет-ретімен тексеру үшін сынаққа бөлу әдісінен сырғаның басты ерекшелігі. 2-ші ғасырдың басындағы кітапта бұл Эратостен Киринейлікке, б.з.д. 3-ші ғасырдың грек математигіне жатқызылған, бірақ олар сынауды бастапқы сандардың орнына тақ сандар арқылы сипаттаған. Бастапқы сандарды табуға арналған көптеген сырғалардың ішінде, бұл кішігірім бастапқы сандарды табудың ең тиімді жолдарының бірі болып табылады. Оны арифметикалық прогрессиядағы бастапқы сандарды табу үшін де қолдануға болады.

Үдемелі сілем

Ішкі жиынтық формулировкасы алғашқы сандарды шексіз (яғни жоғарғы шегі жоқ) түрде, олардың еселіктерін жасау арқылы (соның салдарынан, алғашқы сандар еселіктер арасындағы бос кеңістіктерде табылады) жасайды, мұнда әрбір алғашқы сан p-нің еселіктері тікелей p-нің квадратынан бастап p (немесе жұп емес алғашқы сандар үшін 2p) қадамдарымен санау арқылы жасалады. Генерацияны тек алғашқы санның квадратына жеткен кезде бастау керек, тиімділікке кері әсерін болдырмау үшін. Бұл дерек ағыны парадигмасы бойынша символдық түрде келесідей көрсетілуі мүмкін:

primes = [2, 3, ] \ [[p², p²+p, ] for p in primes],

мұнда \ тізімдік түсініктілік белгісі, арифметикалық прогрессиялардың жиынтығын шегеруді білдіреді. Алғашқы сандарды, сонымен қатар, тізбектелген алғашқы сандармен, бір уақытта бір алғашқы санмен, бөлінгіштік тесті арқылы құрама сандарды итеративті түрде алып тастау арқылы да жасауға болады. Бұл Эратоспеннің елегі емес, бірақ онымен жиі шатастырады, тіпті Эратоспеннің елегі құрама сандарды сынаудың орнына тікелей жасайды. Алғашқы сандардың диапазонын жасауда, сынамалық бөлу Эратоспеннің елегінен нашар теориялық күрделілікке ие. Ол Эратоспеннің елегінің мысалы ретінде жиі ұсынылады. Кездейсоқ қолжетімділік машинасының моделінде n-ден төменгі барлық алғашқы сандарды есептеудің уақыт күрделілігі O(n log log n) операциясы, бұл алғашқы гармоникалық қатардың асимптотикалық түрде log log n-ге жақындауының тікелей салдары. Дегенмен, ол кіріс мөлшеріне қатысты экспоненциалдық уақыт күрделілігіне ие, бұл оны псевдополиномиалды алгоритмге айналдырады. Негізгі алгоритмге O(n) жад қажет. Алгоритмнің биттік күрделілігі O(n (log n) (log log n)) биттік операциясы, жад талаптары O(n). Әдетте іске асырылатын беттік сегменттелген нұсқасы сегменттелмеген нұсқамен бірдей операциялық күрделілікке ие, бірақ кеңістікті сегмент бетінің өте аз мөлшеріне дейін азайтады, сонымен қатар негізгі алғашқы сандарды сақтау үшін қажетті жад мөлшері, құрамаларды іріктеу үшін қолданылатын диапазонның квадрат түбірінен кіші. Негізгі оңтайландырулары бар, Эратоспеннің елегінің арнайы (сирек, егер іске асырылса) сегменттелген нұсқасы O(n) операцияны және жад биттерін қолданады. Үлкен O белгісін қолдану тұрақты факторларды және практикалық диапазон үшін өте маңызды болуы мүмкін ауытқуларды ескермейді: Эратоспеннің өзгеруінің елегі Притчард дөңгелек елегі деп аталады. Ол да 2-ден n-ге дейінгі сандардың тізімімен басталады. Әр қадамда бірінші элемент келесі алғашқы сан ретінде анықталады, тізімнің әрбір элементімен көбейтіледі (осылайша өзінен басталады) және нәтижелер кейіннен өшіру үшін тізімде белгіленеді. Бастапқы элемент пен белгіленген элементтер жұмыс ретімен алынып тасталады, ал процесс қайталанады:

using list comprehension notation with \ denoting set subtraction of arithmetic progressions of numbers. Primes can also be produced by iteratively sieving out the composites through divisibility testing 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 complexity than that of the sieve of Eratosthenes in generating ranges of primes. is often presented as an example of the sieve of Eratosthenes The time complexity of calculating all primes below n in the random access machine model is O(n log log n) operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches log log n. It has an exponential time complexity with regard to input size, though, which makes it a pseudo polynomial algorithm. The basic algorithm requires O(n) of memory. The bit complexity of the algorithm is O(n (log n) (log log n)) bit operations with a memory requirement of O(n). The normally implemented page segmented version has the same operational complexity of O(n log log n) 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
A special (rarely, if ever, implemented) segmented version of the sieve of Eratosthenes, with basic optimizations, uses O(n) operations and bits of memory. Using big O notation ignores constant factors and offsets that may be very significant for practical ranges: The sieve of Eratosthenes variation known as the Pritchard wheel sieve It, too, starts with a list of numbers from 2 to n 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:

[2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79
[3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79
[4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79
[5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79
[ ]

Мұнда мысал алгоритмнің бірінші кезеңінен кейін тақ сандардан басталады. Осылайша, kth қадамында kth алғашқы санның қалған барлық еселіктері тізімнен алынып тасталады, содан кейін тек алғашқы k алғашқы сандармен тең сандар болады (сәйкесінше, тізім келесі алғашқы саннан басталады, ал оның бірінші элементінің квадратынан төменгі сандары да алғашқы сан болады). Осылайша, алғашқы сандардың шектелген тізбесін жасағанда, келесі анықталған алғашқы сан жоғарғы шектің квадрат түбірінен асып кеткенде, тізімдегі қалған сандардың бәрі алғашқы сан болады. Жоғарыда берілген мысалда 11-ді келесі алғашқы сан ретінде анықтап, 80-тен кем немесе оған тең барлық алғашқы сандардың тізімін беру арқылы қол жеткізіледі. Бір қадамда тасталатын сандар сол қадамдағы еселіктерді белгілеу кезінде әлі де қолданылатынын ескеріңіз, мысалы, 3-тің еселіктері үшін 1=3 × 3 = 9, 1=3 × 5 = 15, 1=3 × 7 = 21, 1=3 × 9 = 27, 1=3 × 15 = 45, , сондықтан мұнымен айналысу кезінде абай болу керек.