Прости числа и факторизация

Prime Numbers and Factorization

Какво е просто число?
Колко прости числа има?
Колко често се срещат?
Oсновната теорема на аритметиката.
Проверка за простота на число.
Решето на Ератостен.
Факторизация.
Интересни факти (предположения).
Приложения.
Автор: Соня Милева

В състезания по информатика освен НОД и НОК, друга много често срещана математическа задача е намирането на прости числа, както и факторизацията на число на неговите прости множители. Простите числа имат много важна роля в модерната криптография, генерирането на псевдослучайни числа, и хеширащите алгоритми.

Какво е просто число?


Просто число е всяко естествено число по-голямо от 1, което има за делители само 1 и себе си. Такива числа са например: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71...
!Забележете, че 1 не е просто число – това е една от най-честите грешки при търсенето на прости числа. Затова винаги проверявайте дали функцията, която проверява дали число е просто, не го счита като просто!

Колко прости числа има?

Колко прости числа има? Да допуснем, че има N прости числа. Ако умножим всички тях и добавим 1, резултатът няма да се дели на никое от тези числа (ще дава остатък 1). От тук следва, че това число също е просто, при това е по-голямо от всяко от тези числа → множеството на простите числа е с едно повече от предположеното, което е противоречие с допускането. И тъй като тази процедура може да продължава до безкрай стигаме до извода, че има безброй прости числа.

Колко често се срещат те?

Но колко често се срещат? Лесно се забелязва, че колкото по-малко е числото, толкова по-голям шанс има то да е просто (от 2 до 5 имаме три прости и едно съставно число), но това е вярно само за малките стойности. При по-големи числа простите такива са сравнително равномерно разпределени. Оказва се, че за достатъчно големи X вероятността X да е просто е около 1/log(X).

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

?Ползвайки свойството, че произведението на две прости числа може еднозначно да се "разбие" до една единствена двойка прости числа, е основна част от работата при една от най-разпространените криптографски техники - Public-key cryptography.
Изключителната важност на простите числа за теория на числата и математиката произлиза от основната теорема на аритметиката, която гласи, че всяко естествено число, по-голямо от 1, може да бъде представено по единствен начин (ако не взимаме под внимание реда на множителите) като произведение от прости числа.

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

Наивният алгоритъм за проверка дали дадено число N е просто е да обходим всички числа от 2 до N/2 и да проверим дали N се дели на някое от тях. Този алгоритъм ще има сложност O(N).
bool
isPrimeNaive(
int
N) {
if
(N
<
2
)
return
false
;
for
(
int
i
=
2
;
i
<
=
N
/
2
;
i
+
+
) {
if
(N
%
i
=
=
0
)
return
false
;
}
return
true
;
}

По-бързият алгоритъм е да проверяваме за числата до корен от N (ако до там не сме срещнали делител на N, то е ясно, че N е просто), който ще прави много по-малко операции. Той ще има сложност O(sqrt(N)).
bool
isPrimeFast(
int
N) {
if
(N
<
2
)
return
false
;
int
maxN
=
(
int
)sqrt((
double
)N)
+
1
;
for
(
int
i
=
2
;
i
<
=
maxN
;
i
+
+
) {
if
(N
%
i
=
=
0
)
return
false
;
}
return
true
;
}
Стандартен начин да избегнем ползването на функцията sqrt() (а и да си спестим един ред) е да ползваме следната дребна модификация:
bool
isPrimeFast(
int
N) {
if
(N
<
2
)
return
false
;
for
(
int
i
=
2
;
i
*
i
<
=
N
;
i
+
+
) {
if
(N
%
i
=
=
0
)
return
false
;
}
return
true
;
}

Решето на Ератостен

Решетото на Ератостен е ефективен начин за намиране на всички прости числа до някаква граница.
Алгоритъмът за намиране на простите числа по-малки или равни на N, използвайки решето на Ератостен е следният:
  1. Декларираме масив от тип bool с N+1 елемента, като инициализираме всички негови клетки с true;
  2. Променяме стойностите на клетките 0 и 1 на false - тези числа по дефиниция не са прости;
  3. В нарастващ ред търсим клетките, които все още са със стойност true. При всяко намиране на такава клетка (да кажем със стойност k) отбелязваме клетките k * 2, k * 3, k * 4, ..., ≤ N като false - очевидно те не са прости, тъй като се делят на k;
  4. В края на алгоритъма всички клетки, които са все още със стойност true са на индекси, които са прости числа.
Този алгоритъм може да ни бъде полезен ако трябва да проверим за много числа дали са прости и размерът на числата е разумно голям (за да можем да направим масив с такава големина), тъй като всяка проверка след генерирането на масива ще е константна O(1), а целият алгоритъм има сложност O(N∙log(logN)).
const
int
MAX_NUMBER
=
1000000
;
bool
prime[MAX_NUMBER
+
1
]
;
void
erathosten() {
for
(
int
i
=
0
;
i
<
=
MAX_NUMBER
;
i
+
+
) { prime[i]
=
true
;
} prime[
0
]
=
prime[
1
]
=
false
;
for
(
int
i
=
2
;
i
<
=
MAX_NUMBER
;
i
+
+
) {
if
(prime[i]) {
for
(
int
j
=
i
+
i
;
j
<
=
MAX_NUMBER
;
j
+
=
i) { prime[j]
=
false
;
} } } }

Забележете, че в горния код можем да направим две оптимизации (всъщност, без тях дадената сложност от O(N∙log(log(N)) не е вярна - едва ползвайки тях тя бива достигната).

Първо, ползвайки същото наблюдение като и при "оптимизирания" наивен алгоритъм, можем да въртим външния цикъл само до sqrt(N) - всяко по-голямо просто число би "маркирало" единствено клетки, които вече са маркирани от по-малки такива.

Второ, с аналогични наблюдения можем да стигнем до извода, че вътрешният цикъл няма да върши никаква работа в първите си няколко итерации (примерно ако текущото просто число е 41, то няма нужда да маркираме {41 * 2, 41 * 3, 41 * 5, ..., 41 * 37} като съставни, тъй като вече ще сме ги маркирали докато сме разглеждали, съответно, {2, 3, 5, ..., 37}. Следователно, можем да започваме цикъла едва от текущото число на квадрат.

Така оптимизираната версия на кода става:
const
int
MAX_NUMBER
=
1000000
;
bool
prime[MAX_NUMBER
+
1
]
;
void
erathostenFast() {
for
(
int
i
=
0
;
i
<
=
MAX_NUMBER
;
i
+
+
) { prime[i]
=
true
;
} prime[
0
]
=
prime[
1
]
=
false
;
for
(
int
i
=
2
;
i
*
i
<
=
MAX_NUMBER
;
i
+
+
) {
if
(prime[i]) {
for
(
int
j
=
i
*
i
;
j
<
=
MAX_NUMBER
;
j
+
=
i) { prime[j]
=
false
;
} } } }

Факторизация

Факторизация на естествено число означава разлагане на прости множители. Например 6 = 2 * 3, 8 = 2 * 2 * 2, 12 = 2 * 2 * 3, 42 = 7 * 2 * 3. От основната теорема на аритметиката знаем, че това разлагане е уникално до реда на простите множители.

За да факторизираме едно число N имаме алгоритъм със сложност O(sqrt(N)).
vector
<
int
>
factor(
int
N) {
vector
<
int
>
factors
;
for
(
int
i
=
2
;
i
*
i
<
=
N
;
i
+
+
) {
while
(N
%
i
=
=
0
) { factors.push_back(i)
;
N
/
=
i
;
} }
if
(N
>
1
) { factors.push_back(N)
;
}
return
factors
;
}

Факторизация на много числа

Понякога се налага да факторизирате много на брой числа. За да направите това бързо, трябва да се ползва същия трик както беше и с намирането на много на брой прости - някакъв вид "решето". В случая вместо true/false ("просто"/"съставно") решетото ще пази информация за някой (произволен) прост делител на индекса. Тоест индекс 11 ще пази 11 (единственият прост делител), а индекс 42 може да пази 2, 3, или 7 (някой от трите различни прости делителя на 42).
int
sieve[MAX]
;
void
getFacts() {
for
(
int
i
=
0
;
i
<
MAX
;
i
+
+
) sieve[i]
=
i
;
for
(
int
i
=
2
;
i
*
i
<
MAX
;
i
+
+
) {
if
(sieve[i]
=
=
i) {
for
(
int
c
=
i
*
i
;
c
<
MAX
;
c
+
=
i) sieve[c]
=
i
;
} } }
vector
<
int
>
factor(
int
num) {
vector
<
int
>
factors
;
while
(num
>
1
) { factors.push_back(sieve[num])
;
num
/
=
sieve[num]
;
}
return
factors
;
}
В следната задача за изчислението на функцията f() се налага да имате факторизацията на аргумента. Тъй като той е между 1 и 5000000, горната модификация на решетото на Ератостен (съответно бързата факторизация) са начина за решаването ѝ.

Интересни факти (предположения)

Съществуват няколко хипотези за простите числа. Четири от тях, известни като проблемите на Ландау, са:
?http://xkcd.com/1310/
  • Хипотеза на Голдбах: Всяко четно число, по-голямо от 2, може да се представи като сума на две прости числа.
  • Хипотеза за простите близнаци: Има безкрайно много прости числа p, такива че p + 2 също е просто.
  • Хипотеза на Леджендре: Винаги има поне едно просто число между два последователни точни квадрата.
  • Има безкрайно много прости числа p, такива че p - 1 е точен квадрат.

Приложения

Простите числа често се изпозват за делене по модул, например при хеширащите функции за да се намали вероятността за колизия или при смятане на големи числа. Чести примери са числата 1,000,000,007 и 1,000,000,009.

Удобен туул

Хората, които ползват Linux, могат да отворят shell и да ползват предоставената с него програмка "factor", която факторизира подадения ѝ аргумент на прости множители. Това е полезно и за проверка дали число е просто.

Подобен туул съществува и на informatika.bg: informatika.bg/primes. За съжаление (тъй като е написан на JavaScript, а там максималните числа са от порядъка на 252) той работи само за числа до 1015.

Задачи за тренировка

В задачата Prime Containers трябва просто да имплементирате O(sqrt(N)) проверката дали число е просто. В Primes Matrix пък трябва да използвате Решетото на Ератостен за да намерите кои от числата, които можете да генерирате, са прости, и кои - не, след което с backtrack да намерите всички такива числа, съдържащи се в матрицата. Fractions скрива факта, че за да са взаимно-прости, факторизацията на числителя и знаменателя трябва да не съдържа едно и също просто число - тоест можем да разгледаме само простите числа, в числителя и простите в знаменателя (останалите не ни интересуват).

В Coprimes (Easy) и Coprimes (Hard) трябва да направите наблюдението, че са нужни много малко допълнителни числа за да постигнете изискването на задачата. В Numbers пък трябва да факторизирате голямото число, ползвайки малките такива.

Още задачи

Референции

  1. Прости числа (en.wikipedia.org)
  2. Хипотези на Ландау (en.wikipedia.org)
  3. Онлайн факторизатор (informatika.bg)


За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 29585 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: