Броят на първите делители на число. Колко делители имат първо число?

Всеки ученик знае, че всички номера са разделени на прости и комбинирани. Освен това, тези, които усърдно изучават математиката, са известни и техните свойства. Ако обаче отговорът на въпроса колко делители има първо число е скрит в самата дефиниция на това понятие, тогава е доста трудно да се определи броят на първите делители за дадена. Той се решава с помощта на метода на търсене и вероятностни алгоритми, изпълнявани на компютър.

Малко история

Известно е, че древните гърци са били първите, които проучват свойствата на първостепенните числа. Въпреки това тяхното съществуване е известно от няколко хилядолетия, преди Аристотел да включи теореми за собствеността си в известните си "Принципи". Древните гърци са изобретили и ситото на Ератостен, който е алгоритъм за намиране на prime numbers от интервала [1, n].

През 17-ти век пробив в тяхното проучване Пиер Ферма и Марен Мерсен. Първата формулирана теорема, по-късно кръстена след него, според която всички номера на формуляра 2²ⁿ - просто, доказвайки го за n = 1..4. Но впоследствие Леонард Ойлер показа, че за n = 5 се получава комбиниран номер. Паралелно с това, Марен Мерсен изтъква прости номера на формуляр 2^р - 1, където p е prime. Те са интересни, защото е лесно за тях да проверят спазването на критерия за простота. Като се има предвид този факт, номерата на Mersenne се използват за идентифициране на супер големите първични номера. В момента ограничаването на известните изглежда като 2^77232917 minus- 1.

В допълнение, те се използват широко в разработването на генератори с произволно число, които имат широко приложение на практика.

Легендре и Гаус също играеха важна роля в изучаването на първокачествени номера. Тези учени предложиха хипотеза за тяхната плътност.

Сито Eratosthenes

Ако можем незабавно да се обадим на първите делители на числото 4, после за големи числа обикновено е трудно да се направи това. За решаването на този проблем хората започнаха да мислят преди няколко хиляди години. По-специално, Древногръцки математик Ератостен, който е живял в края на третия и втория век преди Христос, излезе с алгоритъм за намиране на всички първични числа по-малко от цяло число n.

Тя се нарича сито, защото "се издига" или по модерен начин "филтрира" всички номера, с изключение на простите.

Алгоритъмът се състои от следните команди:

1. напишете всички числа от 2 до n;
2. задайте променливата p a стойност 2, тъй като това е най-малкото първо число;
3. да пресече в списъка всички числа от 2p до n, кратни на p;
4. присвоява стойността на променливата p на стойността на първия несрязан номер на записаната последователност, който е по-голям от p;
5. повторете третото и четвъртото възможно най-дълго.

Ако всичко е направено правилно, тогава в списъка всички първични номера от две до n няма да бъдат пресечени.

За осъществяване на сито Eratosthenes на електронен компютър се използва модернизиран алгоритъм. На третата стъпка можете да пресечете номера, започващи с номера p₂, тъй като всички комбинирани числа, които са по-малки от него, по това време вече ще бъдат прекратени. Тогава спирането на работата на алгоритъма трябва да се случи, когато условието p₂п.

Трябва също така да се има предвид, че всички първични номера, с изключение на двойката, са странни, следователно започвайки с p2, можете да "филтрирате" с 2p.

Основната теорема на аритметиката

По дефиниция премиер има два делителя. Един от тях е 1, а вторият е самата стойност.

Преди да разберете какъв е броят на първите делители на число, струва си да отделите малко време, за да изучите основната теорема на аритметиката. Според него естественото число n> 1 може да бъде представено като n = p₁* hellip- sdot- * p_к, където p₁, hellip-, p_m Това са премиерни номера. Освен това такова представяне е уникално до реда на последователността на неговите кофактори.

Последователността на тази теорема може да бъде формулирана по следния начин: всяко естествено число n може да бъде представено във формата n = p₁^d1* стр₂^d2 * hellip- * p_к^гm (в друга формулировка: каноничното разлагане на числото n в прости фактори има формата n = p₁^d1* стр₂^d2* sdot- hellip-sdot- * p_к^гm), където p₁₂< hellip- _m Има прости числа и d₁, hellip-, d_mИма някои естествени числа.

В допълнение, основната теорема на аритметиката, която вече ви е известна, може да бъде преформулирана по следния начин: всяко канонично разлагане на n може да се счита за идентично, ако не се обърне внимание на реда на делителите. Това означава, че на практика за значителен брой числа има много сравнително прости алгоритми за разпадането им в първостепенни фактори, които в крайна сметка дават същия резултат.

Критерият за простота

Преди да разберем как може да се намери най-големият делител на номер (NAP), трябва да се справим с друг важен въпрос.

Така че, нека да разберем по кой алгоритъм е възможно да установим дали има други делители, различни от единица и нейната.

Това може да стане чрез изброяване на първични номера p₁, hellip-р_к. А цикълът може да бъде прекратен веднага щом се появи_{i + 1}, за които е извършена проверката, ще отговаря на условието (пи₊₁)² п.

Нека обясним защо отстраняването може да бъде ограничено до p_аз= sqr (n).

Да предположим, че числото n, изучавано за простота, има някакъв делител p. Тогава d = n / p ще бъде и неговия делител. Но тъй като d и p са различни числа, никой от тях не може да бъде по-голям от корен на n.

Как да намерите най-големия делител на числото n

Намерете NPD n, можете, действайки по следната схема:

• Разделете n на две, ако е равно или три, ако е странно. Единственото изключение е n, последната цифра в десетичната нотация е нула или пет. Такъв номер може веднага да бъде разделен на пет.
• Ако резултатът не е цяло число, разделете n на следните числа, като ги сортирате до p_аз= sqr (n).

Над полученото число n₁ изпълнете всички действия в същия ред, както по-горе, само при условие p_аз= sqr (n₁).

Ако на някоя от стъпките на търсенето, n₁ не е разделена на една от примерите, тогава n е цяло число и е негова собствена NAP. В противен случай получаваме n₂ и продължаваме разделянето с търсене до момента, когато в стъпката (i + 1) установим, че n_аз - цялото.

пример

Да намерим първите делители на числото 276.

• разделете с "две";
• получаваме 138;
• тъй като числото е равно, след това отново се разделя на "две";
• резултатът е 69;
• разделете на следващия номер "три";
• получаваме 23.

Тъй като това число е просто, можем да обобщим. Простите делители 276 са 2, 3 и 23.

Как да намерите броя на първите делители на число

Ако говорим за съвсем малък брой, решаването на такъв проблем не е трудно. Да разгледаме конкретен пример. Да намерим първите делители на числото 54.

За да направите това:

• 54 разделете с "две" и получавате 27;
• 27 е странно, така че вече не го разделяме на "две", а на следващия номер, т.е. "три";
• ние отбелязваме, че 27 = 3³;
• Така разлагането 54 има формата 54 = 2¹ * 3³, т.е. главните делители на числото 54 са "две" и "три".

Това обаче не е всичко, което искахме да знаем. Сега откриваме числото на първите делители на числото 54. То е равно на произведението на правомощията на първостепенните фактори на каноничното разлагане на числото n = p₁*^d1 р₂^d2* sdot- hellip-sdot- * p_m^гm, увеличен с 1. С други думи, в общия случай К = (d₁+1) * ... * (d_m+1).

Тогава за S4 имаме K = 2 * 4 = 8, т.е. общият брой делители е осем.

Имайте предвид, че всичко стана много по-просто, ако говорим за 23, 37, 103 и т.н., тъй като всеки знае колко делители има първо число.

пример

Намерете броя на първите делители на 9990.

• тъй като числото 9990 завършва с числото "нула", то е разделено на пет и две.
• имаме 999.
• в резултат на разделянето от три ние имаме 333;
• отново разделете на три, получаваме 111;
• разделяме на три, имаме 37;
• 37 е първично число, тъй като не може да се дели, без остатък от нито един от първите числа, които са между двойката и корена на числото 37;
• ние броим броя на първите делители на числото 9990. Те са 2,3,5 и 37, т.е. има само четири от тях.

Проблемът с големите числа

Тъй като не е странно, проблемът с намирането на всички първостепенни фактори за даден брой е доста сложен. Фактът е, че досега сме разгледали само номера, чиято десетична бележка се състои от един до четири знака. За тях всички изчисления се извършват на няколко стъпки и те могат да бъдат напълно погълнати, като имат само писалка и лист хартия на ръка. Положението е различно, когато става дума например за 1000-цифрено число. Намирането на всичките си основни фактори ще отнеме повече от един милиард години, дори ако най-мощният суперкомпютър в света ще бъде включен.

Прости номера и защита на информацията

Всеки съвременен човек, който се радва на възможностите, които са възникнали благодарение на появата на локални компютърни мрежи и интернет трябва да защитава поверителността на личните им данни, електронна поща и др. За тази цел се използват криптографски алгоритми с публичен ключ.

При системи с десетки и стотици потребители управление на ключове е сериозен проблем. За да се предотврати манипулирането на ключова информация от нападател, е необходимо да се въведе някаква случайна стойност в процеса на шифроване.

За тази цел най-често срещаните RSA алгоритми използват големи премиални числа.

Има само 10151 първични номера от 1 до 512 бита на дължина. В същото време, за числа, които са близки до n, вероятността произволно избраният брой да бъде проста е 1 / ln n. Така общият брой на prime числата, който е по-малък от n, е равен на n / ln n. Това предполага, че е малко вероятно, че 2 души ще изберат един и същ голям номер.

Тестът Милър-Рабин

За криптографски цели често се използва този вид определение на простотата на числото, което има няколко модификации.

Тестът Милър-Рабин се основава на тестване на редица условия, изпълнявани за числа, които се делят само на 1 и самите те. Ако поне едно от изискванията е нарушено, този номер "изпит" се признава за комбиниран.

За даден m има странни числа t и s, така че m-1 = 2^итет.

След това се избира случайно число а, такова, че 1

Като следствие на теорема Рабин е фактът, че ако R номера, които са избрани на случаен принцип, свидетели призната за определяне primality т, тогава вероятността, че е композит, не може да надхвърля (4^-R).

Сега знаете колко делители имат първо число и как да откриете най-примитивния алгоритъм за изчисляване на НПД. Това знание ще ви помогне да решите много практически проблеми.