Przeglądając blogosferę, natrafiłem niedawno na artykuł o liczbach pierwszych limerykowych. Są to pięciocyfrowe liczby pierwsze postaci AABBA gdzie A i B to dwie różne cyfry, A>0.

Liczb takich jest osiem: 11551, 33113, 33223, 33773, 77447, 77557, 99119, 99559.

Spróbowałem napisać program w Pythonie, który mi te liczby wyszuka. Temat jest banalny, dwie minuty później miałem już gotowca:

from sympy import isprime
results = []
for x in range(10):
    for y in range(10):
        n = 11001*x+110*y
        if(isprime(n)):
            results.append(n)
print(results)

Osiem linii kodu. Oczywiście natychmiast zadałem sobie pytanie czy można to jakoś skrócić. Na przykład, po co zapisywać wyniki pośrednie skoro można je na bieżąco wypisywać na ekran?

from sympy import isprime
for x in range(10):
    for y in range(10):
        n = 11001*x+110*y
        if(isprime(n)):
            print(n)

Co prawda wynik pojawia się teraz w odrobinę innym układzie (każda liczba w osobnej linijce), ale wynik to wynik.

Co by tu dalej... Można zastąpić dwie zagnieżdżone pętle for - jedną:

from sympy import isprime
for x, y in [[x, y] for x in range(10) for y in range(10)]:
    n = 11001*x+110*y
    if(isprime(n)):
        print(n)

Udało nam się zejść do pięciu linii kodu. Co prawda czytelność w linii numer 2 nieco spadła, ale nie ma tragedii. Kolejny pomysł: przełożyć wyliczenie zmiennej n do linii otwierającej pętlę:

from sympy import isprime
for n in [11001*x+110*y for x in range(10) for y in range(10)]:
    if(isprime(n)):
        print(n)

Już tylko cztery linie kodu, wyniki nadal poprawne. Czytelność... mogłaby być lepsza, ale da się to jeszcze w miarę zrozumieć. A co gdyby tak spróbować przefiltrować pod kątem pierwszości listę tworzoną w drugiej linii - w tej samej linii?

from sympy import isprime
for n in list(filter(lambda x: isprime(x), [11001*x+110*y for x in range(10) for y in range(10)])):
    print(n)

Udało nam się zejść do trzech linii kosztem znacznego pogorszenia czytelności. Ale wyniki nadal poprawne, więc kombinujemy dalej.

Hmmmm...

(pięć strzałów znikąd później...)

Hmmmm... Te liczby są raptem tylko pięciocyfrowe, nie potrzebujemy żadnego zaawansowanego algorytmu sprawdzania pierwszości, prawda? Wystarczy podzielić liczbę n przez każdą liczbę od 2 do pierwiastka z n zaokrąglonego w górę do pełnej całości - jeżeli nie dzieli się przez żadną z nich, to jest pierwsza.

Hmmmmmmm...

print(list(filter(lambda n: n>2 and len([i for i in range(2, int(n**0.5)+1) if n%i==0])==0, [11001*x+110*y for x in range(10) for y in range(10)])))

Krócej się już nie da 🙂

Dopisane 2 lata później:

Zapytałem Elemelka czy ma pomysł na krótszy kod i wypluł mi:

print([n for a in range(9)for b in range(10)for n in[11001*(a+1)+110*b]if a-b and all(n%i for i in range(2,n)if i*i<=n)])

Kod jest o 27 znaków krótszy od mojego, więc jednak się dało krócej 🙂