Eratosfen ələyi

Eratosfen ələyi(sieve of Eratosthenes,решето Эратосфена,Eratosthenes eleği)-sadə ədədlərin (təkcə 1-ə və özünə qalıqsız bölünən ədədlərin) axtarışı üsulu. Qədim Yunanıstanda işlənmiş Eratosfen ələyindən kompüterin, yaxud proqramlaşdırma dilinin işləmə sürətini müəyyənləşdirəndə etalon testi kimi istifadə olunur. Bu üsul yoxetmə prosesinə əsaslanır. 2-dən başlamaqla və ədədi öz mövqeyində saxlamaqla proses aşağıdakı kimi gedir:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

  • 2-dən başlayaraq bütün cüt ədədlər (2-nin misilləri) yox edilir:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

  • 3-dən başlayaraq 3-ün misli olan bütün ədədlər yox edilir:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

  • Proses verilmiş ədədlər sırasında ən böyük ədədin kvadrat kökündən böyük olan ədədədək davam etdirilir. Bu halda növbəti ədəd olan 5 sıranın ən böyük ədədi olan 20’nin kvadrat kökündən böyükdür, deməli, proses dayandırılmalıdır. Yerdə qalan bütün yox edilməmiş ədədlər sadədir: 2, 3, 5, 7, 11, 13,17 və 19.
Eratosfen ələyi: 121-dən aşağı başlayan alqoritm addımları (baş kvadratdan başlayaraq optimallaşdırma daxil olmaqla).

Ədəbiyyat

redaktə

Xarici keçidlər

redaktə