Решето Ератосфена.Прості числа[]
Автор статті : Олійниченко Данило.
Тема дослідження []
Проблема дослідження[]
Решето́ Ератосфе́на в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа , що був створений давньогрецьким математиком Ератосфеном.
Гіпотеза дослідження[]
Ми освоемо метод "Решета Ератосфена" для находження простих чисел,але,скоріш за все, не зможемо знайти найбільше просте число.
Мета дослідження[]
Я спробую пояснити закономірність знаходження простих чисел через освоєння методу "Решето Ератосфена".
Хід і результати дослідження []
Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N.
- Перше просте число - два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …).
- Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …).
- Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …).
- Повторюємо операцію поки не буде досягнуто число 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. Доповнення до статті