Проект з математики
ВиконаноБордюгова Анастасією
Сторожовий Яною
Хісемятдіновой Нейл
09.11.2009год
Індійські математики знайшли унікальний алгоритм пошуку простих чисел
Індійські математики та фахівці в галузі комп'ютерного забезпечення заявляють, що розробили метод, що дозволяє безпомилково і швидко визначати, простим чи є та або інша кількість. Проблема швидкого визначення простих чисел, над якою дослідники билися протягом більш ніж 2200 років, є найважливішою в поліпшенні сучасної комп'ютерної техніки.
Прості числа - це ключ до розв'язання багатьох математичних проблем, вони також відіграють велику роль у криптографії (шифруванні), завдяки чому цікавлять не тільки математиків, а й військових, розвідку і контррозвідку. Просте число - те, яке ділиться без залишку тільки на одиницю і на саме себе. Так, до простих чисел належать 2, 3, 5, 7, 11, 13 і так далі по зростаючій.
Першим проблему визначення простих чисел поставив давньогрецький вчений Ератосфен приблизно в 220 році до нашої ери, запропонувавши один із шляхів визначення простих чисел. З тих пір вчені поступово просувалися вперед, а в останні десятиліття їм на допомогу в перевірці подільності величезних чисел прийшли комп'ютери. Математики, а пізніше і фахівці з комп'ютерного програмування розробили багато способів вирішення цієї проблеми, однак всі вони несуть невелику потенційну можливість помилки.
"Наш алгоритм виключає ймовірність будь-якої помилки", - заявив основний розробник нового методу Маніндра Агравал. Результати обчислень вже розіслані провідним комп'ютерним фахівцям і математикам у всьому світі. Вчені еже отримали кілька відгуків. Ніхто не висловлює сумнівів у новому алгоритмі, і всі висловлюють задоволення досягнутим результатом, повідомляє NTVRU.com.
Біографія Ератосфена
Ератосфен Киренський (276 рік до н.е. -194 рік до н.е.) - грецький математик, астроном, географ і поет. Учень Каллімаха, з 235 рік до н.е. - Голова Олександрійської бібліотеки.
Ератосфен-Син Еглаоса, уродженець Кірени.
Початкову освіту Ератосфен отримав в Олександрії під керівництвом свого вченого земляка Каллімаха. Іншим вчителем Ератосфена в Олександрії був філософ лизни. Перебравшись потім в Афіни, він так тісно зблизився зі школою Платона, що звичайно називав себе платоніком. Результатом вивчення наук у цих двох центрах була енциклопедична ерудиція Ератосфена; крім творів з математичних наук, він писав ще трактати «Про добро і зло», про комедію і ін З усіх своїх творів Ератосфен надавав особливе значення суто літературним і граматичним, як це можна укласти з того, що він любив називати себе філологом.
Цар Птолемей III Евергет після смерті Каллімаха викликав Ератосфена з Афін і доручив йому завідування Олександрійської бібліотекою. Віддалений в старості від цієї посади, Ератосфен впав у крайню бідність і, страждаючи хворобою очей або навіть зовсім осліпнувши, заморив себе голодом
Відлуння покликання великої вченості Ератосфена звучать і в прізвиська, які він отримав від сучасників. Називаючи його «бета», вони, за припущенням багатьох дослідників, бажали висловити свій погляд на нього, як на другу Платона, або взагалі як на вченого, який тільки тому займає друге місце, що перше має бути утримано за предками. Іншим прізвиськом Ератосфена було «пентатл»-п'ятиборець.
На честь Ератосфена названий кратер на Місяці.
Решето Ератосфена-алгоритм знаходження всіх простих чисел до деякого цілого числа n, який приписують давньогрецькому математику Ератосфеном Киренському
Алгоритм
Для знаходження всіх простих чисел не більше заданого числа n, дотримуючись методу Ератосфена, потрібно виконати наступні кроки:
1) Виписати поспіль всі цілі числа від 2 до n (2,3,4 ..., n)
2) Нехай змінна p спочатку дорівнює 2-перше просте число.
3) Викреслити зі списку всі числа від 2p до n, що діляться на p (тобто, числа 2p, 3p, 4p, ....)
4) Знайти перший невичеркнутое число, більше, ніж р, і привласнити значенням змінної p це число.
5) Повторювати кроки 3 та 4 до тих пір, поки p не стане більше, ніж n.
6) Всі невичеркнутие числа у списку - прості числа.
На практиці, алгоритм можна трохи поліпшити в такий спосіб. На кроці № 3, числа можна викреслювати, починаючи відразу з числа p 2, тому що всі складені числа менше його вже будуть викреслені до цього часу. І, відповідно, зупиняти алгоритм можна, коли p 2 стане більше, ніж n.
Подільність чисел
Ознаки подільності
Число ділиться на 2 тоді і тільки тоді коли воно закінчується парному цифрою або нулем.
Число ділиться на 3, коли сума цифр числа ділиться на 3.
Число ділиться на 4 тоді і тільки тоді, коли число з двох його останніх цифр (воно може бути двозначним, однозначним або нулем) ділиться на 4.
Щоб дізнатися, чи ділиться двозначне число на 4, можна половину одиниць додати до десятків - якщо сума ділиться на 2, значить, число ділиться на 4.
Наприклад, 92: 9 +1 = 10, значить, 92 ділиться на 4.
Число ділиться на 5, коли воно закінчується на 0 або 5.
Число ділиться на 6 тоді і тільки тоді, коли воно ділиться і на 2, і на 3.
Число ділиться на 7 коли результат віднімання подвоєною останньої цифри, з цього числа без останньої цифри ділиться на 7.
Наприклад, 343:34-3 * 2 = 28 ділиться на 7, значить і число 343 ділиться на 7.
Число ділиться на 8 коли 3 його останні цифри - нулі, або утворюють число яке ділиться на 8.
Щоб дізнатися, чи ділиться 3-значне число на 8, можна половину одиниць додати до десятків. У числа, що вийшло так само - половину одиниць додати до десятків. Якщо підсумкова сума ділиться на 2, значить, число ділиться на 8.
Наприклад, 984:98 +2 = 100 = 10 +0 = 10 ділиться на 2, отже, і число 984 ділиться на 8.
Число ділиться на 9, коли сума цифр числа ділиться на 9.
Число ділиться на 10, коли воно закінчується 0.
Число ділиться на 11, коли сума цифр, з чергуються знаками ділиться на 11.
Наприклад, 271436 ділиться на 11, тому що 6 - 3 + 4 - 1 + 7 - 2 = 11 ділиться на 11.
Число ділиться на 12, коли воно ділиться і на 3, і на 4.
Число ділиться на 13, коли число його десятків, складене з почетвереній числом одиниць, кратно 13 (наприклад, 845 ділиться на 13, так як 84 + (4 * 5) = 104 ділиться на 13).
Число ділиться на 14, коли воно ділиться і на 2, і на 7.
Число ділиться на 15, коли воно ділиться і на 3, і на 5.
Число ділиться на 17, коли число його десятків, складене зі збільшеним у 12 разів числом одиниць, кратно17.
Наприклад, 29053 = 2905 +36 = 2941 = 294 +12 = 306 = 30 +72 = 102 = 10 +24 = 34. Оскільки, 34 ділиться на 17, то і 29053 ділиться на 17.
Ознака не завжди зручний, але має певне значення в математиці. Є спосіб трохи простіше - число ділиться на 17, коли різниця між число його десятків і упятеренним числом одиниць кратна 17.
Число ділиться на 19, коли число його десятків, складене з подвоєним числом одиниць, кратно 19.
Наприклад, 646 ділиться на 19, так як 64 + (6 * 2) = 76 ділиться на 19.
Число ділиться на 23, коли число його сотень, складене з потрійним числом десятків і одиниць, кратно 23.
Наприклад, 28842 ділиться на 23, так як 288 + (3 * 42) = 414; продовжуємо: 4 + (3 * 14) = 46 - очевидно, ділиться на 23.
Число ділиться на 25, коли число, утворене його останніми двома цифрами ділиться на 25 (тобто останні дві цифри утворюють 00,25,50,75).
Розіб'ємо число на групи по 2 цифри справа наліво (у самій лівій групі може бути одна цифра) і знайдемо суму цих груп, вважаючи їх двозначними числами. Ця сума ділиться на 99 тоді і тільки тоді, коли саме число ділиться на 99.
Число ділиться на 100, коли воно закінчується двома нулями.
Розіб'ємо число на групи по 2 цифри справа наліво (у самій лівій групі може бути одна цифра) і знайдемо суму цих груп зі змінними знаками, вважаючи їх двозначними числами. Ця сума ділиться на 101, коли саме число ділиться на 101.
Наприклад, 590547 ділиться на 101, так як 59-05 +47 = 101 ділиться на 101.
Завдання
У деякому царстві, у деякій державі жила принцеса. І одного разу їй захотілося дізнатися відповідь на своє питання про сусідньому королівстві. У сусідньому королівстві було 12 фей. За ніч усім феям треба було виконати однакову кількість бажань. Всього їм треба було виконати 144 бажання. І принцесі захотілося дізнатися, скільки бажань повинна виконати одна фея за ніч. Але щоб дізнатися відповідь на питання, принцесі треба було злітати в сусіднє королівство і запитати у фей. Долетіти до королівства принцеса доручила драконові і дала йому на всю дорогу 6 годин. Відстань до королівства 448,8 км. З якою швидкістю повинен летіти дракон, щоб встигнути злітати і туди, і назад?
Рішення
1) 6:2 = 3 (години) - за такий час дракон повинен злітати туди або назад.
2) 448,8:3 = 149,6 (км / ч) - з такою швидкістю повинен летіти дракон, що прилетіти в своє королівство вчасно.
(Завдання придумала Сторожева Яна).
Дракону треба летіти зі швидкістю 149,6 км / год, що прилетіти в своє королівство вчасно.
Тим часів дракон прилетів в сусіднє королівство. Вирішення питання принцеси виявилося дуже простим:
Рішення
1) 144:12 = 12 (бажань) - повинна виконати 1 фея за ніч.
(Завдання придумала Бордюгова Анастасія).
1 фея повинна виконати 12 бажань за ніч.
Дракон прилетів назад і отримав за відповідь на питання принцеси винагороду: 1,2 кг морозива. Він вирішив поділитися морозивом з друзями. Друзів у нього було 7. Скільки морозива дісталося кожному одному і самому драконові?
Рішення
1) 7 +1 = 8 - друзі і сам дракон.
2) 1,2:8 = 0,15 (кг) - дісталося кожному одному і самому дракону.
(Завдання придумала Хісемятдінова Нейл).
0,15 кг морозива дісталося кожному одному і самому дракону.
Принцеса вирішила покликати до себе на роботу 7 гномів, щоб вони шукали смарагди. І сказала їм, що за тиждень вони повинні знайти 147 смарагдів. А сама принцеса вирішила дізнатися: скільки 7 гномів повинні знайти смарагдів за 1 день? Скільки 1 гном повинен знайти смарагдів за 1 день? Скільки 1 гном повинен знайти смарагдів за тиждень?
Рішення
1) 147:7 = 21 (смарагд) - повинні знайти 7 гномів за 1 день.
2) 21:7 = 3 (смарагду) - повинен знайти 1 гном за 1 день.
3) 3 * 7 = 21 (смарагд) - повинен знайти 1 гном за тиждень.
(Завдання придумала Сторожева Яна).
21 смарагд повинні знайти 7 гномів за 1 день, 3 смарагду повинен знайти 1 гном за 1 день, 21 смарагд повинен знайти 1 гном за тиждень. Гномам треба було десь жити. Принцеса вирішила віддати їм підвал. У підвалі було 476м 2. Скільки кожному гномові має дістатися м 2, щоб кожному гномові дісталося однакову кількість м 2?
Рішення
1) 476:7 = 68 (м 2) - дістанеться кожному гномові.
(Завдання придумала Бордюгова Анастасія).
Кожному гномові дістанеться по 68м 2.
Як-то раз до принцеси прийшла Червона шапочка і сказала, що не вміє ділити. Вона приготувала 381 пиріжок і повинна роздати його 3 своїм бабусям. Але вона не знає, скільки пиріжків має дістатися кожної бабусі. Принцеса стала вважати:
Рішення
1) 381:3 = 127 (пиріжків) - дістанеться кожній бабусі.
(Завдання придумала Хісемятдінова Нейл).
Принцеса сказала Червону шапочку, що кожній бабусі дістанеться по 127 пиріжків. Червона шапочка подякувала принцесу і пішла далі.