Էրատոսթենեսի մաղ

Էրատոսթենեսի մաղ մինչև n որոշակի ամբողջ թիվը եղած պարզ թվերը գտնելու ալգորիթմ, որի հայտագործումը վերագրում են հին հույն մաթեմատիկոս Էրատոսթենես Կիրենացուն։ Ինչպես և մնացած բոլոր դեպքերում, այստեղ ալգորիթմի անունը խոսում է նրա կատարած աշխատանքի սկզբունքի մասին, այսինքն մաղը իրենից ենթադրում է «զտում», այս դեպքում, բացի պարզ թվերից, «զտվում են» մնացած բոլոր թվերը։ Թվերի ցանկով առաջ անցնելիս պարզ թվերը մնում են, իսկ մնացած թվերը, որոնք կոչվում են բաղադրյալ թվեր, հեռացվում են։


== Պատմություն ==
Համաձայն լեգենդի, մեթոդը ստացել է «մաղ» անվանումը, քանի որ Էրատոսթենեսը թվերը գրում էր մոմով պատված փոքրիկ տախտակի վրա, և անցք էր բացում այն տեղերում, որտեղ գրված էին բաղադրյալ թվեր։ Տախտակը նմանեցնում էին մաղի, որի միջոցով մաղում էին բաղադրյալ թվերը և թողնում միայն պարզ թվերը։ Էրատոսթենեսը կազմել է մինչև 1000 եղած պարզ թվերի ցանկը։


== Ալգորիթմ ==

Մինչև տրված n թիվը եղած պարզ թվերը գտնելու համար, համաձայն Էրատոսթենեսի մեթոդի, անհրաժեշտ է կատարել հետևյալ քայլերը՝

Գրել 2-ից մինչև n թիվը եղած բոլոր ամբողջ թվերը (2, 3, 4, …, n)։
Ներմուծել p փոփոխականը, որը հավասար է առաջին պարզ թվին՝ 2-ի։
Ընդգծել 2p-ից մինչև n եղած թվերը, արժեքը ավելացնելով p-ով (ցանկը կլինի հետևյալը՝ p, 2p, 3p, 4p, …)։
Գտնել առաջին p-ից մեծ արժեք ունեցող չընդգծված թիվը, և p փոփոխականին տալ նրա արժեքը։
Քանի հնարավոր է կրկնել 3-րդ և 4-րդ քայլերը։Հիմա 2-ից միինչև n եղած բոլոր չընդգծված թվերը պարզ են։
Գործնականում ալգորիթմը հնարավոր է հեշտացնել հետևյալ ձևով. 3-րդ քայլում թվերը ընդգծել սկսած p2-ից, քանի որ դրանից փոքր բոլոր բաղադրյալ թվերը այդ ժամանակ ընդգծված չեն լինում։ Եվ, համապատասխանաբարորեն ալգորիթմի քայլերը դադարեցնել երբ p2-ը դառնա p-ից մեծ։ Ինչպես նաև, բոլոր պարզ թվերը(բացի 2-ից) կենտ են, այդ իսկ պատճառով, նրանց կարելի է հաշվել 2p քայլով , սկսած p2-ից։


== Ալգորիթմի բարդություն ==
Մինչև 
  
    
      
        n
      
    
    {\displaystyle n}
   եղած պարզ թվերը հաշվելու ալգորիթմի հաշվողական բարդությունը 
  
    
      
        O
        (
        n
        log
        ⁡
        (
        log
        ⁡
        n
        )
        )
      
    
    {\displaystyle O(n\log(\log n))}
   է։


=== Բարդության ապացույց ===
Ընտրված 
  
    
      
        n
        ∈
        
          N
        
      
    
    {\displaystyle n\in \mathbb {N} }
   թվի համար ամեն պարզ 
  
    
      
        p
        ∈
        
          P
        
        :
        p
        ≤
        n
      
    
    {\displaystyle p\in \mathbb {P} \colon p\leq n}
   թվի համար կատարվում է ներքին ցիկլ(կրկնություն), որը կկատարի 
  
    
      
        
          
            n
            p
          
        
      
    
    {\displaystyle {\frac {n}{p}}}
   գործողություն։ Հետևաբար, պետք է գնահատել հետևյալ մեծությունը՝

  
    
      
        
          ∑
          
            p
            ∈
            
              P
            
            :
            p
            ≤
            n
          
        
        
          
            n
            p
          
        
        =
        n
        ⋅
        
          ∑
          
            p
            ∈
            
              P
            
            :
            p
            ≤
            n
          
        
        
          
            1
            p
          
        
      
    
    {\displaystyle \sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {n}{p}}=n\cdot \sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {1}{p}}}
  
Քանի որ 
  
    
      
        n
      
    
    {\displaystyle n}
  -ից փոքր կամ հավասար պարզ թվերի քանակը գնահատվում է որպես 
  
    
      
        
          
            n
            
              ln
              ⁡
              n
            
          
        
      
    
    {\displaystyle {\frac {n}{\ln n}}}
  , ինչի արդյունքում, 
  
    
      
        k
      
    
    {\displaystyle k}
   պարզ թիվը մոտավորապես հավասար է 
  
    
      
        k
        ln
        ⁡
        k
      
    
    {\displaystyle k\ln k}
  , գումարը հնարավոր է գրել այսպես՝

  
    
      
        
          ∑
          
            p
            ∈
            
              P
            
            :
            p
            ≤
            n
          
        
        
          
            1
            p
          
        
        ≈
        
          
            1
            2
          
        
        +
        
          ∑
          
            k
            =
            2
          
          
            
              n
              
                ln
                ⁡
                n
              
            
          
        
        
          
            1
            
              k
              ln
              ⁡
              k
            
          
        
      
    
    {\displaystyle \sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {1}{p}}\approx {\frac {1}{2}}+\sum \limits _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}}
  
Այստեղ գումարից առանձնացվում է առաջին պարզ թիվը, որպեսզի խուսափենք 0 թվի վրա բաժանելուց։ Այսպիսով գումարը հնարավոր է գնահատել հետևյալ ինտեգրալով՝

  
    
      
        
          
            1
            2
          
        
        +
        
          ∑
          
            k
            =
            2
          
          
            
              n
              
                ln
                ⁡
                n
              
            
          
        
        
          
            1
            
              k
              ln
              ⁡
              k
            
          
        
        ≈
        
          ∫
          
            2
          
          
            
              n
              
                ln
                ⁡
                n
              
            
          
        
        
          
            1
            
              k
              ln
              ⁡
              k
            
          
        
        
        d
        k
        =
        ln
        ⁡
        ln
        ⁡
        k
        
          
            
              |
            
          
          
            2
          
          
            
              n
              
                ln
                ⁡
                n
              
            
          
        
        =
        ln
        ⁡
        ln
        ⁡
        
          
            n
            
              ln
              ⁡
              n
            
          
        
        −
        ln
        ⁡
        ln
        ⁡
        2
        =
        ln
        ⁡
        (
        ln
        ⁡
        n
        −
        ln
        ⁡
        ln
        ⁡
        n
        )
        −
        ln
        ⁡
        ln
        ⁡
        2
        ≈
        ln
        ⁡
        ln
        ⁡
        n
      
    
    {\displaystyle {\frac {1}{2}}+\sum _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}\approx \int \limits _{2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}\,dk=\ln \ln k{\Bigr |}_{2}^{\frac {n}{\ln n}}=\ln \ln {\frac {n}{\ln n}}-\ln \ln 2=\ln(\ln n-\ln \ln n)-\ln \ln 2\approx \ln \ln n}
  
Արդյունքում ստանում ենք հետևյալը՝

  
    
      
        
          ∑
          
            p
            ∈
            
              P
            
            :
            p
            ≤
            n
          
        
        
          
            n
            p
          
        
        ≈
        n
        ln
        ⁡
        ln
        ⁡
        n
        +
        o
        (
        n
        )
      
    
    {\displaystyle \sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {n}{p}}\approx n\ln \ln n+o(n)}
  
Ավելի խիստ և հիմնավորված ապացույց հնարավոր է գտնել Hardy и Wright «An Introduction to the Theory of Numbers» գրքում։


== Մեքենայական կոդ ==
Մեքենայական օպտիմալ կոդի իրագործված է հետևյալ կերպ՝

Մուտք։ n բնական թիվ

A — տրամաբանական(բինար) զանգված, ինդեքսավորված 2-ից մինչև  n,սկզբնապես արժևորված true արժեքով։

for i := 2, 3, 4, ..., while i ≤ n:
 if A[i] = true:
for j := i2, i2 + i, i2 + 2i, ..., while j ≤ n:
 A[j] := false

Ելք։ i թվեր, որոնց համար A[i] = true


== Օրինակ n = 30 դեպքի համար ==
Գրենք 2-ից մինչև 30 եղած բոլոր բնական թվերը՝

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

Ցանկում առաջին թիվը՝ 2ը պարզ թիվ է։ Անցնելով ցանկով, ջնջենք 2ին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած 22 = 4-ից )

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

Մյուս չջնջված թիվը՝3ը պարզ է։ Անցնելով ցանկով, ջնջենք 3ին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած 32 = 9-ից )

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

Մյուս չջնջված թիվը՝5ը պարզ է։ Անցնելով ցանկով, ջնջենք 5ին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած 52 = 25-ից ) և այսպես շարունակ՝

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

Մյուս չջնջված թիվը՝ 7, նրա քառակուսին՝ 49 ավելի մեծ է քան 30-ը, այսինքն աշխատանքը ավարտված է և պարզ թվերի ցանկը հետևյալն է՝

2 3 5 7  11  13   17  19   23 29


== Ծանոթագրություններ ==


== Գրականություն ==
Гальперин Г. «Просто о простых числах» // Квант. — № 4.
Под. ред. Невская И.И. Неопубликованные материалы Л.Эйлера по теории чисел. — "Наука", 1997.
Проф. Д.Ф.Егоров Элементы теории чисел. — Государственное издательство Москва, 1923.
Кордемский Б. А. Математическая смекалка. — М.: ГИФМЛ, 1958. — 576 с.


== Արտաքին հղումներ ==
Решето Эратосфена от М. Гарднера
Алгоритм составления таблицы простых чисел от заданного до другого числа
Реализация алгоритма поиска простых чисел на Java
Доказательство сложности алгоритма
Еще раз о поиске простых чисел