10-cio cyfrowa liczba pierwsza, w której jest 7x7

Witam, chcę napisać program który spośród wszystkich liczb dziesięciocyfrowych wybiera największą liczbę która jest liczbą pierwszą i ma w zapisie '7777777' (siedem siódemek obok siebie)

Napisałem taki kod:

def najwieksza():
    n = 9997777777
    while (True):
        if "7777777" in str(n):
            print "."  #niepotrzebna linia - sprawdzam ile razy program wchodzi do pętli
            q = 0
            i = 1
            while (i <= n):
                if (n % i) == 0:
                    q += 1
                    if q > 2:
                        break
                i += 1
        if q == 2:
            print n
            break
           
        n -= 2

Ten program jednak nie działa - wchodzi do pętli 2 razy, ale za drugim razem liczy liczy liczy i nie może się doliczyć. Może ktoś pomóc mi jakoś z tym zdaniem?

no i w czym problem? Nie potrafisz zrobić tego w oparciu o swój poprzedni wątek http://4programmers.net/Forum/Newbie/171508-liczby_pierwsze_majace_obok_siebie_trzy_siodemki?

poczytaj o sicie Eratostenesa, tak na początek Swoją drogą każda liczba jest podzielna przez jeden i samą siebie bez reszty, więc pierwszych w ten sposób nie znajdziesz

sig napisał(a):

poczytaj o sicie Eratostenesa, tak na początek Swoją drogą każda liczba jest podzielna przez jeden i samą siebie bez reszty, więc pierwszych w ten sposób nie znajdziesz

No tak, ale ja przestaje sprawdzać daną liczbę kiedy jest podzielna przez większą ilość liczb niż 2. Kiedy przelecę przez wszystkie możliwość a liczba podzielna jest przez tylko 2 liczby (q == 2) tzn że jest pierwsza. Moje rozumowanie jest chyba w porządku.

Nie rozumiem czego oczekujesz?
Aby ci przeprowadzono formalny dowód że z sitem będzie setki razy szybciej?
Sito Eratostenesa to 3-5 wierszy kodu.

MarekR22 napisał(a):

nie! Masz generować sobie liczby 10cio cyfrowe mające 7 siódemek (będziesz ich miał 1000) i dla nich sprawdzać pierwszoplanowość.

Ale jakim cudem 1000? Przecież mogą być postaci:

7777777xxx
x7777777xx
xx7777777x
xxx7777777

W dla każdego z tych przypadków mam 1000 możliwości czyli łącznie 4000.

Nie zupełnie, 10 cyfrowych będzie 3700 bo zero nie może być pierwszą cyfrą.
3420 - po uwzględnieniu tego co napisał poniżej @Azarien

Za x można podstawiać też 7 co trochę zmniejszy ilość, jeśli nie chcemy tych samych liczb liczyć wielokrotnie.

http://www.wolframalpha.com/input/?i=primes+%3C+100000
Czyli warto się zastanowić nad testem Millera-Rabina
Bo test podstawowy może być powolny dla tak dużych liczb.

Jeśli możecie, to podpowiedzcie mi jeszcze jak generować liczby mające w sobie 7 siódemek? Nie mam za bardzo pomysłu jak to zrobić.

Florian napisał(a):

Jeśli możecie, to podpowiedzcie mi jeszcze jak generować liczby mające w sobie 7 siódemek? Nie mam za bardzo pomysłu jak to zrobić.

Akurat to jest proste, https://docs.python.org/2/library/itertools.html#itertools.combinations_with_replacement. Generujesz 3 cyfrowe kombinacje znaków od 0 do 9, i władasz im w wszystkie możliwe miejsca te siódemki. Przy okazji sprawdzasz czy wygenerowania jest pierwsza, i drukujesz największą z tych co okażą się pierwsze.

No dobra czyli ogólnie tak: Za pomocą 3 pętli for tworzę sobie wszystkie kombinacje cyfr od 0 do 9 i zapisuję te kombinacje do listy. Później tworzę drugą listę w której dopisuję na wszystkie możliwe sposoby 7x7. Na końcu sprawdzam od największej która jest pierwsza.

Od razu w tych pętlach możesz to sprawdzić, tylko że trzeba nieco się zastanowić.