Prime Numbers and Sieve of Eratosthenes.hy.md

Խնդիր համար 3 - Ի՞նչպես ստուգել թիվը պարզ է թե բաղադրյալ, ի՞նչպես գտնել մինչև տրված թիվը եղած բոլոր պարզ թվերը և «Էրատոսթենեսի մաղի» ալգորիթմը (Sieve of Eratosthenes):

Նախ բերեք վերհիշենք, թե որ թվերն են կոչվում պարզ թվեր։ Եվ այսպես մաթեմատիկայում պարզ թվերը բնական թվեր են, որոնք ունեն միայն երկու բաժանարար, այսինքն առանց մնացորդի բաժանվում են միայն 1-ի և հենց իրենց վրա։ Օրինակ՝ 7-ը պարզ թիվ է, այն բաժանվում է միայն 1-ի և 7- վրա, իսկ 8-ը՝ ոչ, որովհետև այն առանց մնացորդ բացի 1-ից և 8-ից, բաժանվում է նաև 2-ի և 4-ի վրա։

Սկզբից ստեղծենք ֆունկցիա, որը կստուգի թե արդյոք մուտքագրված թիվը պարզ է։ Ամենապարզ տարբերակով, տվյալ ֆունկցիան կունենա հետևյալ տեսքը՝

function isPrime(num) {
  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return num > 1;
}

Ֆունկցիայի մեջ ստեղծում ենք ցիկլ, որը պետք է տվյալ թիվը հերթով բաժանի մինչև այդ թիվը եղած բոլոր բնական թվերի վրա։ Ցիկլի մեջ ստուգում ենք, եթե մուտքագրված թիվը առանց մնացորդի բաժանվում է i-ի վրա, ուրեմն այն պարզ թիվ չէ, և իմաստ չկա էլ շարունակել։ Հետևաբար ֆունկցիան դադարեցնում է աշխատանքը և վերադարձնում է false: Եթե if-ի պայմանը չի կատարվում, ուրեմն թիվը պարզ է, և մի փոքրիկ ստուգում անելով` num > 1, վերադարձնում ենք արդյունքը։ Այդ ստուգման նպատակը ինչպես հասկացաք բացասական թվերի բացառումն է, պարզ թիվը կարող է լինել միայն դրական և ամբողջ։ Մենք կարող ենք մի փոքր բարելավել ֆունկցիան։ Անիմաստ է շարունակել ցիկլի աշխատանքը, եթե մինչև մուտքագրված թվի քառակուսի արմատը չկան բաժանարարներ։ Այսինքն եթե մինչև այդ թիվը բաժանարարներ չկան, ապա հետո հաստատ չեն լինի։ Ցիկլի պայմանի մեջ ստեղծում ենք ևս մեկ փոփոխական, և անվանվում օրինակ max: Այն որպես արժեք ընդունելու է մուտքագրված թվի քառակուսի արմատը։

Մի փոքր փոփոխված, բարելավված ֆունկցիան կունենա հետևյալ տեսքը՝

function isPrime(num) {
  for (let i = 2, max = Math.sqrt(num); i <= max; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return num > 1;
}

Այժմ փորձենք ստանալ մինչև մուտքագրված թիվը եղած բոլոր պարզ թվերի բազմությունը։ Դրա համար անհրաժեշտ է ստեղծել դատարկ զանգված, և ցիկլի միջոցով ստուգելով մինչև մուտքագրված թիվը եղած բոլոր թվերը, առանձնացնել պարզ թվերը և հերթով ավելացնել զանգվածի մեջ։ Ֆունկցիան կունենա հետևյալ տեսքը՝

function getPrimes(num) {
  const primes = [];
  for (let i = 2; i < num; i++) {
    if (isPrime(i)) {
      primes.push(i);
    }
  }
  return primes;
}

Ֆունկցիան հիանալի աշխատում է,ճշգրիտ վերադարձնելով մինչև մուտքագրված թիվը եղած բոլոր պարզ թվերը։ Բայց այն մի փոքրիկ թերություն ունի, քանի որ ցիկլի մեջ ամեն անգամ կանչում է isPrime ֆունկցիան, որի մեջ իր հերթին նորից ցիկլ է աշխատում, ստացվում է ցիկլ ցիկլի մեջ, և ֆունկցիայի աշխատանքի արագությունը զգալի դանդաղում է։ Միջին հզորության համակարգչի վրա մինչև 1 միլիոն թվի համար այն համարյա ակնթարթային արդյունք է տալիս, բայց եթե փորձենք ավելի մեծ թվեր, հապաղումը ակնհայտ տեսնելու ենք։

Մենք կարող ենք ֆունկցիան վերափոխել, օգտագործելով «Էրատոսթենեսի մաղի» ալգորիթմը։ Իսկ սկզբից փորձենք հասկանալ թե այն ինչ է իրենից ներկայացնում։ Ալգորիթմի անվանումից կարող ենք ենթադրել, որ այն աշխատում է զտման սկզբունքով՝ հեռացնելով բոլոր բաղադրյալ թվերը, և թողելով միայն պարզերը։ Իրականում հենց այդպես էլ լինում է, եթե մենք օրինակ վերցնենք 2-ը, ապա ակնհայտ է, որ 2-ին բազմապատիկ բոլոր թվերը այլևս չեն կարող պարզ լինել։ Հետևաբար եթե մեզ պետք է մինչև 10-ը եղած պարզ թվերի բազմությունը, մենք կարող ենք համարձակորեն դեն նետել 4, 6, 8 թվերը՝ նրանք հաստատ բաղադրյալ են և կարիք չկա ստուգելու։ Հաջորդ պարզ թիվ 3-ի բազմապատիկները նույնպես դեն ենք նետում՝ մեր օրինակում 9-ը(6-ն էլ 3-ի բազմապատիկ է, բայց այն արդեն դեն ենք նետել, քանի որ նաև 2-ի բազմապատիկն է): Համաձայն լեգենդի, այս եղանակը առաջին անգամ հայտնագործել է Էրատոսթենես Կիրենացին և այն ստացել է «մաղ» անվանումը, քանի որ Էրատոսթենեսը թվերը գրում էր մոմով պատված փոքրիկ տախտակի վրա, և անցք էր բացում այն տեղերում, որտեղ գրված էին բաղադրյալ թվեր։ Տախտակը նմանեցնում էին մաղի, որի միջոցով մաղում էին բաղադրյալ թվերը և թողնում միայն պարզ թվերը։ Էրատոսթենեսը նաև կազմել է մինչև 1000-ն եղած պարզ թվերի ցանկը։

Հիմա փորձենք մեր getPrimes(num) ֆունկցիան վերակառուցել՝ օգտագործելով Էրատոսթենեսի ալգորիթմը։ Մեզ անհրաժեշտ կլինի ստեղծել ևս մեկ դատարկ զանգված, որտեղ կպահենք «մաղված», «զտված» բաղադրյալ թվերի բազմությունը։ Թարմացված ֆունկցիան կունենա հետևյալ տեսքը՝

function getPrimes(num) {
  const seive = [];
  const primes = [];

  for (let i = 2; i <= num; i++) {
    if (!seive[i]) {
      primes.push(i);
      for (let j = i * i; j <= num; j += i) {
        seive[j] = true;
      }
    }
  }
  return primes;
}

Կարող եք կոնսոլում փորձել, անգամ 10 մլն մուտքագրելու դեպքում շատ արագ վերադարձնում է մինչև 10 մլն-ն եղած բոլոր պարզ թվերի զանգվածը։