Решето ератосфена в програмуванні
Відео: №2 PascalABC NET Прості числа Решето Ератосфена Частина 1 Програма курсу програмування Курси
Математика - наука, яка з`явилася кілька тисяч років і активно використовувалася вже в Стародавній Греції. При цьому багато вчених-теоретиків, які жили в той час, робили відкриття, що стали великими і геніальними, але справжнє визнання отримали кілька століть тому, коли технології дозволили зрозуміти весь потенціал досліджень античних арифметиков. Варто відзначити, що всі розрахунки в далеких епохах велися «в умі» або містили в собі масштабні записи обчислень. Одним з найвідоміших грецьких фахівців був Ератосфен, негласно названий прапрадедушкой програмування. З появою інформатики саме його розрахунки, теорії та аксіоми нерідко перетворювалися в комп`ютерні «мови». В арсеналі математика було кілька цікавих відкриттів, але найбільш поширеним стало решето Ератосфена, що допомагає швидко знайти просте число з представленої послідовності.
біографія вченого
Незважаючи на те що вся діяльність фахівця відбувалася на території Стародавньої Греції, народився майбутній геній в Африці в третьому столітті до нашої ери. Навчався вчений в найбільших містах Греції, де і залишився жити на постійній основі. Його викладачами були відомі поети, філософи і граматики того часу.
Завдяки різнобічному розвитку і поваги в колі однодумців геніальний теоретик запрошується на посаду бібліотекаря Олександрії, де і прослужив до самої смерті, створюючи неймовірні для тієї епохи опуси і дослідження в різних областях, в тому числі решето Ератосфена. Сучасник вченого - легендарний Архімед - відгукувався про нього тільки в листяних тонах і навіть присвятив його роботі окремий працю.
Відео: №2 PascalABC NET Прості числа Решето Ератосфена Частина 1 Курси програмування для школярів
досягнення
Головною особливістю античного вченого по праву вважається різнобічність досліджуваних напрямків. При цьому практично у всіх сферах він домігся видатних результатів. Філософія, поезія, математика, астрономія, музика, філологія, географія - за такий унікальний універсалізм в пошуку знань теоретик отримав прізвисько пентатле, по асоціації зі спортивним багатоборством. Звичайно, він не став великим в одній з досліджуваних областей, але в кожній з них виходило досягти непоганих результатів.
Про це говорять збереглися фрагменти його праць і досліджень. Незважаючи на перебування в деякій тіні своїх сучасників, вчений зробив величезний внесок в історію математики, а решето Ератосфена з рядом інших відомих розрахунків по праву стало на одну сходинку зі знаменитими геометричними і арифметичними відкриттями.
Історія назви і подробиці перебування
В античні часи всі записи, в тому числі математичні викладки проводилися на спеціальних табличках з воску. Тому при розрахунках алгебраїчного і арифметичного характеру, особливо під час виключення цифр в послідовності, вчені «виколювали» їх на письмових приладді.
Після всіх робіт табличка нагадувала предмет домашнього начиння, за що дослідження і було названо - решето Ератосфена. Поштовхом до відкриття послужили думки генія про знаходження простих чисел в натуральному ряду. Роботи тривали кілька місяців, поки не був досягнутий остаточний результат. У третьому столітті до нашої ери він став справжнім проривом.
Що являє собою алгоритм?
Швидкий спосіб знайти все прості числа в натуральному ряду цікавили вчених з незапам`ятних часів. Адже вони не мають суворої послідовності і розташовані в умовно-випадковому порядку. На даний момент фахівці багато в чому розібралися і навчилися виробляти потрібні обчислення досить швидко. У цьому їм допоміг нехитрий алгоритм - решето Ератосфена. Античний геній відкрив його в кілька етапів:
- Береться натуральний ряд від одного до будь-якої цифри (універсальний термін N) Варто відзначити, що кілька тисячоліть тому одиниця вважалася простим числом. Зараз його відносять до особливого виду, який не має строгого визначення.
- Далі відбувається викреслювання всіх чисел, що діляться на двійку.
- Потім береться перше з решти (в даному випадку трійка) і виключають все цифри, які діляться на нього.
- Розрахунок триває до останнього числа в послідовності.
- Що залишився ряд буде містити тільки прості показники.
Такий варіант довгий час вважався єдино ефективним, а з появою інформатики фахівці змогли робити обчислення більш складних послідовностей. При цьому навіть з новими технологіями решето Ератосфена є найважливішою математичної теорією.
Мови програмування в сфері арифметичних розрахунків
Технології, комп`ютери і інформатика дозволили математикам, що вивчають алгебраїчні теорії, вийти на новий етап розвитку науки. Насамперед, скориставшись унікальною можливістю, вони стали інтегрувати відомі арифметичні і геометричні дослідження в програмування. Одним з найбільш затребуваних електронно-обчислювальних мов в той момент став, в тому числі для розрахунку алгоритму решето Ератосфена, Паскаль. З його допомогою за кілька секунд можна було знаходити прості числа в послідовності натуральних чисел, які довгий час були недоступні або обчислювалися шляхом грандіозних записів, займаючи багато часу. У підсумку, практична база нового потенціалу отримала покращений варіант античного відкриття і практичні безмежні можливості розрахунків.
Використання на сучасних Олімпіадах з інформатики
На даний момент проведення змагань для школярів з різних предметів знову набирають популярність. Лауреати та переможці таких заходів виходять на новий рівень навчання і можуть отримати непогані перспективи в подальшій діяльності, в тому числі матеріальні гранди.
Олімпіади з інформатики включають в себе не тільки складні завдання, але і знаходження таких відомих понять, як прості числа. Решето Ератосфена при цьому використовується як найбільш актуального способу обчислення послідовностей, шляхом інтегрування аксіоми в програмний код. Незважаючи на стародавність відкриття, дана теорія допомагає швидко і ефективно освоїтися в важкодоступних розрахунках.
