re.match(r"^1?$|^(11+?)\1+$", "1" * num) == None <=> num е просто
- Частта
^1?$match-ва нула или една единици. Съответно ако
num == 0илиnum == 1ще има match и => резултатът отre.matchняма да е None
=> резултатът от изразът ще бъде False, което е коректно поведение,
тъй като 0 и 1 не са прости числа. - Частта
^(11+?)\1+$върши същинската работа.
групата(11+?)търси 2 или повече единици по non-greedy начин
(опитва се да хване възможно най-малко единици).\1+пък търси
едно или повече повторения на вече намерената група. Ако се намерят
такива едно или повече повторения, примерноk >= 1,
то следва, че в целият низ"1" * numимак+1 >= 2групи от еднакъв брой единици
(например от m единици) иm >= 2. Получихме k групи po m единици.
Тогаваnum == k*mи е съставно.
Ако пък няма match =>"1" * numне може да се разбие на групи единици с равен
брой елементи <=> num няма делители.
Това че използваме non-greedy match-ване значи, че на практика
обхождаме възможните дължини на групи във възходящ ред.
Ако не се направи това изразът ще хванеnum//2единици и така
пропускаме проверката на доста от възможните делители.
Важно е да се отбележи, че и двете части почват с ^ и завършват с $
<=> проверяваме само целият string.
...
Изглежда че, да напишем краен автомат за мачване на regex-и е
едно от най-яките приложения на курса по ЕАИ.
Така е... било по времето на grep 
.
В Python и всички други езици,
в които ще ги ползвате, regex parser-ите са реализирани с рекурсивен backtracking,
който компилира израза в нещо като суфиксно дърво.
Добавят се и референции "назад"(ребра назад? whatever...),
които са извън регулярните езици и нямат представяне като крайни автомати.
Тези оптимизации постигат по-ефективна машина на състоянията бла бла бла.
Частта с тъпия пример: искаме да мачнем aaaaab|aaaaac|aaaaad. Компилираният израз е aaaaa[b|c|d]
И толкова, в по-сложни примери е твърде вероятно това да е по-бързо и определено ще е по-чисто от решения с for цикли.
[Disclaimer] Peanut and bullshit traces may appear in this post