regex_prime_checker обяснение

  1. 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.

  2. Извинявам се за коментара, това отговор на някакъв въпрос ли е - например- как да използваме Unary numeral system за проверка дали число е просто или ?! Иначе намерих два линка по темата, който лично на мен ми помогнаха да схвана обяснението ти :

    линк 1 с примери

    линк 2

  3. И понеже имаше доста ентусиасти да дисектират regex-ите :fork_and_knife: ... Изглежда че, да напишем краен автомат за мачване на regex-и е едно от най-яките приложения на курса по ЕАИ. Така е... било по времето на grep :trollface:. В Python и всички други езици, в които ще ги ползвате, regex parser-ите са реализирани с рекурсивен backtracking, който компилира израза в нещо като суфиксно дърво. Добавят се и референции "назад"(ребра назад? whatever...), които са извън регулярните езици и нямат представяне като крайни автомати. Тези оптимизации постигат по-ефективна машина на състоянията бла бла бла. Частта с тъпия пример: искаме да мачнем aaaaab|aaaaac|aaaaad. Компилираният израз е aaaaa[b|c|d] И толкова, в по-сложни примери е твърде вероятно това да е по-бързо и определено ще е по-чисто от решения с for цикли. [Disclaimer] Peanut and bullshit traces may appear in this post

Трябва да сте влезли в системата, за да може да отговаряте на теми.