Кът на програмиста...

[Corwin]

Моридине, аз си се оправих с моя регексп, обаче кат си машина искам да се пробваш да ми обясниш как работи следното нещо, щот досега никой не е успял...

sub is_prime {
my ($number) = @_;
return (1 x $number) !~ m/\A (?: 1? | (11+?) (?> \1+ ) ) \Z/xms;
}

[The Dragon]

Не работи. Ако функцията си отговаря на името.

[Corwin]

Работи си.
Връща истина ако подаденото число е просто. Писала го е Абигейл, една психопатка дето е контрибютнала милион модули в ЦПАН. Аз лично съм го виждал в "Best Perl Practices", ама май е печелила някво състезание с него...

[The Dragon]

А дали връща само тогава?

[Corwin]

Code:

Spoiler: show

sub is_prime {
my ($number) = @_;
return (1 x $number) !~ m/\A (?: 1? | (11+?) (?> \1+ ) ) \Z/xms;
}

for my $current_num ( 1 .. 100 ) {
if ( is_prime($current_num) ) {
print "$current_num - Prime\n";
}
}

Output:

Spoiler: show

[corwin@corwin ~/myshits/scripts]$ perl regexpr.pl
2 - Prime
3 - Prime
5 - Prime
7 - Prime
11 - Prime
13 - Prime
17 - Prime
19 - Prime
23 - Prime
29 - Prime
31 - Prime
37 - Prime
41 - Prime
43 - Prime
47 - Prime
53 - Prime
59 - Prime
61 - Prime
67 - Prime
71 - Prime
73 - Prime
79 - Prime
83 - Prime
89 - Prime
97 - Prime

[Corwin]

* Your mom is so fat she sat on a binary tree and turned it into a linked list in constant time!
* Saying Java is good because it works on all OSes is like saying anal sex is good because it works on all genders.
* Q: "What is the object oriented way of getting rich?" A: Inheritance

[shayhiri]

От информатика разбирам нула, но не закачайте а***ния се*с.

[Marfa]

Ае, не че нещо, ама какво му е на секса, че се нуждае от звездичка насред себе си?

[shayhiri]

off
Това е смокиновото листо върху голямото К в средата.

Де да знам, от приличие. Иначе се радвам, че си от нашта партия.
/off

[Morwen]

[offtopic]И откога секс е неприлична дума, значи? И къде е приличието да говориш за нещо и на всички да им е ясно за какво, но да си извърташ езика, та да не могат да те кажат, че си говорел точно за него?
[/offtopic]
Не ми е ясно точно как програмистката тема успя да се оспами със сексуални спорове, но може би не е зле някой модератор да попремести в пералнята излишното...

[Moridin]

Стига сте спамили ;р

Як изглежда изразът, ама сега съм на мийтинг
по-късно

[thunder]

плакат е, за това в спойлерче

Spoiler: show

[Moridin]

Измислих го, хитричко е Доста нестандартен подход, макар и леко хамалски Но като цяло тъмбс ъп.

Идеята е следната -

Spoiler: show

числото N, с което започваме, се преобразува в N на брой единици. Това се прави от пърл-ския код.

Самият регулярен израз прави всъщност нещо много просто - проверява дали числото има делители. Ако има делители (т.е. имаме match), числото е съставно. Ако няма (т.е. няма match - затова и условието е !~), числото е просто.

Проверката става по следния начин:
Изразът има две алтернативи - едната е частта "1?", другата е частта "(11+?)(?> \1+)". Целият израз е ограден в група, за да сложим отпред и отзад ограничителите за място \A и \Z (още известни като ^ и $). Тази група има ?: отпред, за да не се брои при номерацията на backreferences, т.е. групираме само за синтактично удобство, без да запазваме резултата, match-нат от групата.

Така. Първата част намира като съвпадение вариантите празен стринг (N=0) и една единица (N=1). Тези две числа не се броят за прости в математиката и затова трябва да се укажат тук като "съставни" (не че са и съставни).

Втората част практически обхожда числата над 1 (представени като низ от единици с "11+", т.е. с поне две единици), като за всяко проверява дали до края на низа има точен брой повторения на това число. Ако това е така - значи числото N точно се дели на число, по-голямо от 1 и по-малко от самото него, и следователно е съставно. Ако изразът фейлне при целия бектракинг - значи няма съвпадение и числото е просто.

За пример да вземем N=6. То генерира низа "111111". Първата алтернатива на израза отпада, понеже N>1. След това първата група (11+?) хваща подниза "11" в началото. Прави така, понеже имаме lazy quantifier, т.е. ще вземе най-малкия подниз, който удовлетворява израза в скобите. След това идва веселата част - търсим до края точен брой повторения (+) на запазеното в първите скоби (\1). При нас това се получава! Имаме остатък "1111", което са две повторения на низа "11", който в текущия момент се пази от първата група и към него сочи референцията "\1". Така имаме повторение и значи числото е съставно.

Сега да вземем N=5. При него това няма да стане, защото остатъкът от низа е "111". Групата "11" се повтаря веднъж и удовлетворява "\1+", но след това регулярният израз свършва, а в низа има още една единица. Съвпадението пропада и машината започва да бектраква. При това групата \1 сега ще пази "111" - следващият lazy match. Сега остатъкът е "11" и няма повторение. Пропада - пак бектрак, при който \1 става "1111" - пак същото, и при "11111" - пак. Целият израз пропада и следователно 5 е просто число.

И остана да изясня за какво служи това "?>" във вторите скоби. Ами пести доста бектракинг. При 5 и 6 това не се вижда, но да вземем за пример N=7. Тогава след провала на мачването на повторения с група \1="11", машината няма да бектрекне до това да присвои на групата "111" (следващата стъпка от lazy matching-а на първия подизраз), а първо ще се опита да намали обхвата на greedy matching-а на втория подизраз (\1+), т.е. оригинално то е намерило две повторения и се е провалило след това, сега ще счита запазеното във втората група като само едно повторение на \1 и ще започне да чете пак до края израза. В нашия случай това е безсмислено - няма значение колко са повторенията, а само дали точно изчерпват остатъка от низа, или не. При това след тази втора група от повторения няма нищо друго в израза. Ние знаем това, но машината не го знае. За това този бектракинг ни бави излишно - спестяваме го, като слагаме "?>" отпред на втората група. С този синтаксис постигаме нещо като "cut" при Prolog - забраняваме повече бектракинг ВЪТРЕ в границите на тази група, т.е. веднъж мачната, тя вече се счита за атомарен елемент, а не за подизраз, който може още да бъде мачван и бектракван.

Хм... абе май се виждаше и при 5 както и да е.

п.п. опциите зад израза, както и \A и \Z би трябвало да са ясни Специално опцията "х" позволява да има интервали в израза и те да се игнорират от парсъра на автомата за израза.

п.п.2. По молба на Роумър слагам обяснението в спойлър, че да се мъчи грешната му душа да гадае

[thunder]

еййй, за една задача в хаккуест използвах нещо подобно, но можах да се вместя в 3-те секунди време за излисление (много голямо число беше там)

много яко, сега го пуснах тука Не е нормална тази Абигейл

[Moridin]

А коя е Абигейл и отде знаем, че изразът е неин?