Прости числа и факторизация
Prime Numbers and Factorization
Какво е просто число?
Колко прости числа има?
Колко често се срещат?
Oсновната теорема на аритметиката.
Проверка за простота на число.
Решето на Ератостен.
Факторизация.
Интересни факти (предположения).
Приложения.
Колко прости числа има?
Колко често се срещат?
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. |
Проверка за простота на число
Наивният алгоритъм за проверка дали дадено число 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, използвайки решето на Ератостен е следният:
- Декларираме масив от тип
bool
с N+1 елемента, като инициализираме всички негови клетки сtrue
; - Променяме стойностите на клетките 0 и 1 на
false
- тези числа по дефиниция не са прости; - В нарастващ ред търсим клетките, които все още са със стойност
true
. При всяко намиране на такава клетка (да кажем със стойност k) отбелязваме клетките k * 2, k * 3, k * 4, ..., ≤ N катоfalse
- очевидно те не са прости, тъй като се делят на k; - В края на алгоритъма всички клетки, които са все още със стойност
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 пък трябва да факторизирате голямото число, ползвайки малките такива.
Още задачи
Референции
- Прости числа (en.wikipedia.org)
- Хипотези на Ландау (en.wikipedia.org)
- Онлайн факторизатор (informatika.bg)
За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 29585 пъти.