FANDOM


Решето Ератосфена.Прості числаРедагувати

Автор статті : Олійниченко Данило.

Тема дослідження Редагувати

Проблема дослідження Редагувати

Решето́ Ератосфе́на в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа , що був створений давньогрецьким математиком Ератосфеном.

Гіпотеза дослідження Редагувати

Ми освоемо метод "Решета Ератосфена" для находження простих чисел,але,скоріш за все, не зможемо знайти найбільше просте число.

Мета дослідження Редагувати

Я спробую пояснити закономірність знаходження простих чисел через освоєння методу "Решето Ератосфена".

Хід і результати дослідження Редагувати

Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N.

  1. Перше просте число - два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …).
  2. Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …).
  3. Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …).
  4. Повторюємо операцію поки не буде досягнуто число N:
    • Наступне незакреслене число є простим. Викреслимо всі числа більші нього та кратні йому.

Числа, які залишилися незакресленими після цієї процедури - прості[1].

Розглянемо приклад для n = 20

Запишемо натуральні числа від 2 до 20 в рядок:

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

Перше число в рядку 2 — просте. Викреслимо всі числа кратні 2 (кожне друге, починаючи з ):

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

Наступне незакреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з ):

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

Наступне незакреслене число 5 — просте. Викреслимо всі числа кратні 5 

(кожне п’яте, починаючи з ). І т. д.

Необхідно викреслити кратні для всіх простих чисел , для яких . В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для  вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими.

Алгоритм решета Ератосфена у вигляді програми на псевдокоді для пошуку простих чисел менших

1 000 000 :

limit = 1000000
 // початково вважаємо, що всі числа прості
 // присвоєння змінній типу стрічка символів ''sieve$''  рядка, який складається з 1000000 літер "Р",
 sieve$ = string of the character "P" with length limit
 
 prime = 2  // 2 – перше просте число
 
 repeat while prime² < limit 
 // зміна літер "Р", порядковий номер (індекс) яких кратний ''prime'' (за виключенням індекса ''prime''), на "N" 
 set the character at the index of each multiple of ''prime'' (excluding index ''prime'' * 1) in ''sieve$'' to "N"
 // змінній ''prime'' присвоюється індекс наступної "Р" в стрічці ''sieve$''
 prime = index of the next instance of "P" in ''sieve$'' after index ''prime''
 end repeat


Висновки Редагувати

Мені дуже сподобалося проводити дослідження з простими чісламі.Я спробував «вловити», відсіяти прості числа від складових, користуючись «Решетом Ератосфена»

Корисні ресурси Редагувати

Weisstein, Eric W. Sieve of Eratosthenes(англ.) на сайті Wolfram MathWorld. Доповнення до статті

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Відвідайте інші вікіпроекти на Вікія!

Випадкова вікі