A regular expression to check for prime numbers

Hozzászólások

Trükkös - a Perl-féle regexp többletét nem ismerem.

Ha van jot telepítve (és pcre2), akkor

jot -s '' 13 1 1 | pcre2grep -q '^1?$|^(11+?)\1+$' || echo Prím

A (nem túl gyors) gépemen 79621-nél már kb. 2 másodperc, 209929-nál meg kb. 12 másodperc.

Nem nagyon értem a jot-os sorodat. Kiírja, hogy prím, ellenben ha ezt írom:

jot -s '' 13 1 1 | factor

akkor az bizony azt mondja, hogy van felbontása, szóval nem prím.

Illetve valami nem kerek. Direkt felraktam a gnugrep csomagot - az ugyanis ismeri a -P opciót pont a Perl-regexp-ekhez, és az is így működik. Még a végén valami csalafintaság van, és mégse jó ez a regexp, vagy én nézek be valamit de nagyon?

No jól van. Ha az ember odafigyelve olvas, akkor lehet, hogy érti is. Szóval nem a jot kimenetéről dől el, hogy prím-e, hanem a jot első paraméteréről (már a -s '' utáni számról). Azaz a regex az egymás utáni egyesek darabszámát teszteli. (FreeBSD alatt tesztelni akartam a pcre2grep -et meg a gnugrep-et, hogy van-e futásidejű különbség - hát erre a gnugrep is libpcre2-t használ, és értelemszerűen nem lett látványos különbség.)

Jaja, kell egy kis idő, míg leesik. Röviden: annyi darab egyes kell, amelyik számot tesztelni akarod (persze az egyesnek nincs jelentősége, lehetne bármi más karakter is). Ezután a regexp gyakorlatilag azt nézi (az 1 db egyes esetét leszámítva), hogy igaz-e a mintára, hogy legalább kétszer végigmegy egy legalább kettő hosszú sorozat (azaz felírható-e két darab kettőnél nagyobb-egyenlő szám szorzataként).

A jot első paramétere pedig az ismétlődések számát adja meg, a második és harmadik pedig a kezdő és a végső értéket az ismétlődésben, azaz pl. a 13-nál a 13 darab egyest kapja meg a regexp - persze a 13 darab egyesből álló 13-jegyű szám lehet, hogy nem prím.

i=1 ; while [ "$i" -le 100 ] ; do echo -n 1 ; i=`expr "$i" + 1` ; done

Ekkor teljesen Bourne-shell. Vagy persze lehet

for i in {1..100} ; do echo -n 1 ; done

is. Ezt a formát ismeri a modernebb bash, a yash, meg a ksh93 is, szóval tűrhetően hordozható.

De, a backtickkel nincs semmi gond, tudja kb minden shell (azt még a C-shell is kezeli ebben a formájában), bár egy db. jot parancs helyett egy for ciklus seq-kel már erősen öntökönlövés. Persze a while benne az expr-rel pláne az - ha a cél a külső parancsok számának minimalizálása, akkor talán az lehet a kompromisszum, hogy használjuk a modernebb shellekben levő aritmetikai operátort / helyettesítést ( pl.) :

i=1; while [ "$i" -le 100 ] ; do echo -n 1 ; i=$(( i + 1 )) ; done

Mondjuk ez így már nem klasszik Bourne-.shell.

Egyszerűbben:

a jot az BSD-izm, a seq pedig Linuxizm.

Óvatosan azért az {x..y} használatával. A shell (legalábbis a Bash) először kifejti az {x..y}-t, azaz behelyettesíti az összes lehetséges értéket. Ez {1..100} esetén egy modern gépen nem igazán vehet észre, {1..1000000} esetén már beletelik némi időbe és {1..100000000} esetén meg a gépem magába roskadt és csak Magic-SysRq-val sikerült jobb belátásra bírnom.

Ha az erőforrás nem is számít akkor is érdemes tudni ha túl nagy az érték akkor visszaadja az eredeti inputot, pl:

~ $ echo {1..4}
1 2 3 4
~ $ echo {1..18446744073709551616}
{1..18446744073709551616}

Bash esetén javasolt az alábbi formát használni (azt azért érdemes észben tartani hogy, ha jól emlékszem, a Bash csak 64 bites számokat kezel, szóval utána csendben átcsordul):

for(( I=0; I<100; I++ ))

Általános esetben meg lehet while-t használni.