Проект по математике
Выполнен
БордюговойАнастасией
СторожевойЯной
ХисемятдиновойНейлей
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, числа можно вычеркивать,начиная сразу с числа p2, потому что все составные числаменьше его уже будут вычеркнуты к этому времени. И, соответственно,останавливать алгоритм можно, когда p2 станетбольше, чем 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 пирожков. Красная шапочкапоблагодарила принцессу и пошла дальше.