Алгоритм нахождения простых чисел

Проект по математике

Выполнен

Бордюговой Анастасией

Сторожевой Яной

Хисемятдиновой Нейлей

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², потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p² станет больше, чем 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м². Сколько каждому гному должно достаться м², чтобы каждому гному досталось одинаковое количество м²?

Решение

1) 476:7=68(м²)- достанется каждому гному.

( Задачу придумала Бордюгова Анастасия).

Каждому гному достанется по 68м².

Как-то раз к принцессе пришла Красная шапочка и сказала, что не умеет делить. Она приготовила 381 пирожок и должна раздать его 3 своим бабушкам. Но она не знает, сколько пирожков должно достаться каждой бабушке. Принцесса стала считать:

Решение

1) 381:3=127 (пирожков)- достанется каждой бабушке.

( Задачу придумала Хисемятдинова Нейля).

Принцесса сказала Красной шапочке, что каждой бабушке достанется по 127 пирожков. Красная шапочка поблагодарила принцессу и пошла дальше.