Първо число | естествено число от определен вид

Как да намерим малки прости числа

Съществува прост метод за намиране на списък с прости числа. Създал го е Ератостен. Наречен е Сито на Ератостен. Той улавя числата, които не са прости (като сито), и пропуска простите числа.

Методът работи със списък от числа и със специално число, наречено b, което се променя по време на метода. При преминаването през метода някои числа се ограждат в кръг, а други се зачеркват. Всяко обходено число е просто, а всяко зачеркнато число е съставно. В началото всички числа са обикновени: не са закръглени и не са зачеркнати.

Методът винаги е един и същ:

1. На един лист хартия напишете всички цели числа от 2 до проверяваното число. Не записвайте числото 1. Преминете към следващата стъпка.
2. Започнете с b, равно на 2, и преминете към следващата стъпка.
3. Обърнете кръгче b в списъка. Преминете към следващата стъпка.
4. Като започнете от b, пребройте още b в списъка и зачеркнете това число. Повторете броенето на още b числа и зачеркването им до края на списъка. Преминете към следващата стъпка.
• (Например: Когато b е 2, ще закръглите 2 и ще зачеркнете 4, 6, 8 и т.н. Когато b е 3, ще закръглите 3 и ще зачеркнете 6, 9, 12 и т.н. 6 и 12 вече са зачеркнати. Зачеркнете ги отново.)
5. Увеличете b с 1. Преминете към следващата стъпка.
6. Ако b е зачеркнато, върнете се към предишната стъпка. Ако b е число в списъка, което не е зачеркнато, преминете към 3-та стъпка. Ако b не е в списъка, преминете към последната стъпка.
7. (Това е последната стъпка.) Готови сте. Всички прости числа са закръглени, а всички съставни числа са зачеркнати.

Например този метод може да се приложи за списък с числата от 2 до 10. В края на краищата числата 2, 3, 5 и 7 ще бъдат оградени с кръгчета. Това са прости числа. Числата 4, 6, 8, 9 и 10 ще бъдат зачеркнати. Това са съставни числа.

Този метод или алгоритъм отнема твърде много време за намиране на много големи прости числа. Въпреки това той не е толкова сложен, колкото методите, използвани за много големи прости числа, като например теста за първичност на Ферма (тест, с който се проверява дали дадено число е просто или не) и теста за първичност на Милър-Рабин.

За какво се използват простите числа

Първичните числа са много важни в математиката и информатиката. Много дълги числа са трудни за решаване. Трудно е да се намерят техните прости коефициенти, затова в повечето случаи числата, които вероятно са прости, се използват за криптиране и секретни кодове. Например:

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

• Ако някой има цифров подпис за своя имейл, се използва криптиране. Това гарантира, че никой не може да фалшифицира имейл от него. Преди подписването се създава хеш стойност на съобщението. След това тя се комбинира с цифровия подпис, за да се получи подписано съобщение. Използваните методи са повече или по-малко същите като в първия случай по-горе.

• С течение на годините намирането на най-голямото известно просто число се е превърнало в своеобразен спорт. Проверката дали едно число е просто може да бъде трудна, ако числото е голямо. Най-големите първични числа, известни във всеки един момент, обикновено са първични числа на Мерсен, тъй като най-бързият известен тест за първичност е тестът на Лукас-Лемер, който разчита на специалната форма на числата на Мерсен.

Свързани страници

• Коприме
• Списък на простите числа
• Палиндромно просто число
• Първична факторизация
• Wilson prime