Znajdowanie 10-cyfrowych liczb pierwszych

Witam,

Mam takie zadanie do rozwiązania:

Liczba pierwsza jest hiperszczęśliwa, jeżeli zawiera co najmniej 7 siódemek pod rząd. Napisz program, który wypisuje największą dziesięcocyfrową hiperszczęśliwą liczbę pierwszą. Postaraj się, by Twój program można było łatwo zastosować w innym, po dobnym zadaniu (przy innej liczbie cyfr i innej liczbie siódemek czyniących liczbę hiperszczęśliwą). Program powinien zakończyć działanie w kilkanaście sekund.

I nie wiem do końca jak znajdować te 10 cyfrowe liczby pierwsze tak żeby nie przekroczyć czasu na wykonanie zadania. Jaka będzie najszybsza metoda znajdowania 10 cyfrowych liczb pierwszych.

Przygotuj sobie wcześniej zestaw liczb pierwszych zawierających siódemki. Z takim gotowym zestawem danych odnalezienie "najfajniejszej" to pikuś.

Więc najlepiej będzie znaleźć te liczby pierwsze sitem Eratostenesa, następnie sprawdzenie czy mają 7 i potem wyszukanie największej?

Czym sobie znajdziesz to absolutnie nie jest ważne.
Cały trick polega na tym, żebyś w swoim kodzie szukającym hiperszczęśliwych liczb miał >gotowy< (wcześniej przygotowany) zbiór liczb pierwszych.
coś w rodzaju primes = [ danych w cholere ]

Ja bym jednak sprawdzał czy kolejne duże liczby z siedmioma 7 pod rząd są pierwsze czy nie.

Udało mi się napisać coś takiego lecz program nadal jest zbyt wolny proszę o jakieś rady jak go poprawić.

from math import sqrt
import random
 
def fermat(k, p):
    i = 0
    while i < k:
        a = random.randint(1, p - 1)
        if pow(a, (p - 1), p) == 1:
            i = i + 1
        else:
            return False
    return True

def prime(n):
    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
            break
        i += 1
    return True

counter = 0

for i in range(9999999999, 1000000000, -2):
    if '7777777' in str(i):
        if fermat(5,i):
            if prime(i):
                
                counter += 1
            
        

Program powinien zwrócić odpowiedź w kilka(dziesiąt) sekund, mam wypisać ile jest takich liczb 10-cyfrowych hiperszczęśliwych.

Panie, fermata tu wrzuciłeś a dalej szukasz dzielników wśród liczb parzystych? :D I sprawdzasz też liczby parzyste jako potencjalnie pierwsze? o_O Litości!
Proponowałbym jednak dorzucić tam sito żeby nie marnować czasu na liczby które ewidentnie nie są pierwsze.

No i wiesz że python to nie jest demon szybkości? Odpal to pod PyPy jeśli już chcesz w pythonie. Ale przepisanie tego do C spowoduje pewnie przyspieszenie przynajmniej 10 razy? Ale najpierw popraw ten algorytm...

Rozwiąż wariant zadania z liczbami hiperszczęśliwymi. W tym wariancie nie interesuje nas największa liczba hiperszczęśliwa, lecz to, ile jest 10-cyfrowych liczb
pierwszych hiperszczęśliwych. Program powinien zwrócić odpowiedź w kilka(dziesiąt) sekund.

Po zalecanych modyfikacjach wykonanie programu trwa około 40 min, więc dużo dużo za wolno. W zadaniu jest napisane, że ma to trwać kilkadziesiąt sekund, więc może jest jakiś inny szybszy sposób na rozwiązanie tego zadania? Znalazłem 203 takie liczby. Aktualny kod wygląda tak:

from math import sqrt
import random
 
def fermat(k, p):
    i = 0
    while i < k:
        a = random.randint(1, p - 1)
        if pow(a, (p - 1), p) == 1:
            i = i + 1
        else:
            return False
    return True

def prime(n):
    i = 3
    while i*i <= n:
        if n % i == 0:
            return False
            break
        i += 2
    return True

counter = 0

for i in range(9999999999, 1000000000, -2):
    if '7777777' in str(i) and i % 3 != 0 and i % 5 != 0 and i % 7 != 0:
        if fermat(5,i):
            if prime(i):
                counter += 1
            
print(counter)

Ciągle nie ma "sita" a takowe dało by programowi prawdziwego kopa.

o_O ale przecież ty masz znaleźć pierwszą, bo największą. U mine na pypy to działa praktycznie momentalnie:

import random

import itertools
import timeit


def fermat(k, p):
    for i in range(k):
        a = random.randint(1, p - 1)
        if pow(a, (p - 1), p) != 1:
            return False
    return True


def prime(n):
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True


def main():
    for i in itertools.count(9999999999, -2):
        if i < 1000000000L:
            break
        if '7777777' in str(i) and i % 3 != 0 and i % 5 != 0 and i % 7 != 0:
            if fermat(5, i) and prime(i):
                print i
                break


main()

Rozumiesz w ogóle polecenie tego zadania?

4.5 sek na Cpythonie, 2.5sek na PyPy.

Znaj moją łaskawość, bo zadanie ciekawe:

import random
import itertools
import timeit


def fermat(k, p):
    for i in range(k):
        a = random.randint(1, p - 1)
        if pow(a, (p - 1), p) != 1:
            return False
    return True


def prime(n):
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True


def generate_data():
    mid = '7777777'
    prefix_len = 0
    suffix_len = 3
    data = set()
    while suffix_len >= 0:
        prefixes = ["".join([str(x) for x in p]) for p in itertools.product(range(10), repeat=prefix_len) if
                    p and p[0] != 0]
        if not prefixes:
            prefixes = ['']
        suffixes = ["".join([str(x) for x in s]) for s in itertools.product(range(10), repeat=suffix_len)]
        for prefix in prefixes:
            for suffix in suffixes:
                n = int(prefix + mid + suffix)
                data.add(n)
        suffix_len -= 1
        prefix_len += 1
    return data


def main():
    counter = 0
    for i in generate_data():
        if fermat(5, i) and prime(i):
            # print('found number', i)
            counter += 1
    print(counter)


main()
# print(timeit.timeit("main()", number=1))

2s na PyPy, 4.5s na Cpythonie.

Dość prymitywny program z "sitem", 12s

tab = [2, 3, 5]

def czypierw(liczba):
	for pierwsza in tab:
		if pierwsza * pierwsza > liczba:
			tab.append(liczba)
			return True
		if liczba % pierwsza == 0:
			return False
	tab.append(liczba)
	return True


for i in range(7, 100000):
	czypierw(i)


baza = "7777777"
for i in range(10000000000, 999999999, -1):
	if baza in str(i):
		if czypierw(i) is True:
			print(i)
			break

@sig ech po pierwsze to autor rozwiązuje teraz zupełnie inny problem. Po drugie rozwiązanie które proponowałem wcześniej działa w ~2s. No i to co napisałeś to wcale nie jest sito tylko trochę ulepszone trial-division bo dzielisz tylko przez dzielniki będące liczbami pierwszymi w danym zakresie. Obok sita to nawet nie leżało ;] Ba, ty nawet sita nie użyłeś do wyznaczenia tego zbioru potencjalnych dzielników, a akurat by się nadało do tego ;]

Ja bym generował tak:

def generate_data():
    data = set()
    for sufix in range(1000):
        data.add(7777777000 + sufix)
    for sufix in range(100):
        for prefix in range(1,10):
            data.add(prefix*1000000000 + 777777700 + sufix)
    for sufix in range(10):
        for prefix in range(10,100):
            data.add(prefix*100000000 + 77777770 + sufix)
    for prefix in range(100,1000):
        data.add(prefix*10000000 + 7777777)
return data

Zmienna data zawiera 3420 liczb, u @Shalom`a jest 3700 (bo są powtórzenia), czas wykonania mojego kodu jest minimalnie krótszy.
Wersja zmodyfikowana, łatwiejsza do adaptacji:

data = set()
middle = 7777777
prefix_len = 0
suffix_len = 3

while suffix_len >= 0:
    base = middle*(10**suffix_len)
    power = (10**(10 - prefix_len))
    for sufix in range(10**suffix_len):       
        for prefix in range(int(10**(prefix_len - 1)),int(10**prefix_len)):
            data.add(prefix*power + base + sufix)
    suffix_len-=1
    prefix_len+=1

Poniżej sekundy, ale mam jakiegoś buga w generatorze liczb z siódemkami (niektóre mają o jedną cyfrę za mało)

import math

ilecyfr = 10
ilesiod = 7

tab = [2, 3, 5]


def czypierw(liczba):
	for pierwsza in tab:
		if pierwsza * pierwsza > liczba:
			tab.append(liczba)
			return True
		if liczba % pierwsza == 0:
			return False
	tab.append(liczba)
	return True

reszta = ilecyfr - ilesiod
maxzak = int("9" * reszta) + 1
minzak = int("1" + "0" * (reszta - 1))
pierw = int(math.ceil(math.sqrt(maxzak)) + 1)
wynik = 0

for i in range(7, pierw):
	czypierw(i)


baza = ilesiod * "7"
for liczba in range(minzak, maxzak):
	liczba = str(liczba)
	for i in range(len(liczba)):
		tymcz = int(liczba[i:] + baza + liczba[:i])
		if czypierw(tymcz):
			if tymcz > wynik:
				wynik = tymcz

print(wynik)

@sig nadal nie przeczytałeś drugiego polecenia. Akurat znaleźć największą liczbę to nie problem bo wystarczyłoby lecieć od max do min i wybrać pierwszą znalezioną. Nie wiem po co przelgądasz wszystkie. No i tyle było pisania o tym sicie :P Mogłeś sobie tą tablicę tab[] policzyc sitem właśnie ;)

BTW nie wiem czy wiecie ale operacje na zmiennych globalnych są dużo wolniejsze niz na lokalnych. Wrzućcie to sobie wszystko do funkcji i będzie jeszcze szybciej.

Przystosowanie dla innej ilości cyfr w liczbie i siódemek załatwiają 2 pierwsze zmienne z main-a (wcześniej były globalnymi), a sprawdzam wszystkie bo moim zdaniem w innym przypadku generator byłby przekombinowany. Trzeba by osobno rozważać "dodatek" z cyfr mniejszych i większych od siódemki (w zależności od tego większe były by z siódemkami wcześniej albo dalej). Oto obecny kod z funkcjami. Żadnych dodatkowych zaleceń mam nadzieję nie przegapiłem.

import math


def generuj(minzak, maxzak, ilesiod):
	baza = ilesiod * "7"
	for liczba in range(minzak, maxzak):
		liczba = str(liczba)
		for i in range(len(liczba)):
			tymcz = int(liczba[i:] + baza + liczba[:i])
			yield(tymcz)


def czypierw(liczba):
	tab = [2, 3, 5]
	for pierwsza in tab:
		if pierwsza * pierwsza > liczba:
			tab.append(liczba)
			return True
		if liczba % pierwsza == 0:
			return False
	tab.append(liczba)
	return True


def main():
	ilecyfr = 10
	ilesiod = 7
	reszta = ilecyfr - ilesiod
	maxzak = int("9" * reszta) + 1
	minzak = int("1" + "0" * (reszta - 1))
	pierw = int(math.ceil(math.sqrt(maxzak)) + 1)
	wynik = 0

	for i in range(7, pierw):
		czypierw(i)
	for liczba in generuj(minzak, maxzak, ilesiod):
		if czypierw(liczba):
			if liczba > wynik:
				wynik = liczba
	print(wynik)

main()

ps próbowałem zrobić osobną funkcję dla sprawdzenia czy liczba jest pierwsza, ale dodanie tab-a do jednej sprawdzającej przyśpiesza program względem 2 i globalnej listy tab.

a sprawdzam wszystkie bo moim zdaniem w innym przypadku generator byłby przekombinowany. Trzeba by osobno rozważać "dodatek" z cyfr mniejszych i większych od siódemki (w zależności od tego większe były by z siódemkami wcześniej albo dalej).

Rzeczywiście, dopisanie na końcu instrukcji

sortedData = sorted(data)

bardzo "przekombinowuje" generator.

Dzień dobry,
@Shalom sprawdziłem Twój kod (ostatnia odpowiedź na pierwszej stronie) na liczenie ile jest tych 10-cyfrowych liczb hiperszczęśliwych (po wyniku sądzę, że to właśnie do tego drugiego zadania program),
w moim programie jest dokładnie ten sam wynik-225(1.6s), ale mam problem z powtarzającym się sprawdzaniem liczb które mają w sobie więcej niż 7 siódemek - ale nie o mój kod mi chodzi, bo to jest jeszcze do poprawienia, otóż drugi program - mniej sprytny - działa 46minut ale wypisuje wynik 203.. Wydaje mi się, że to jednak 203 jest bliżej prawdy, więc chciałem Cię spytać, czy jesteś pewny wyniku w swoim programie?

@Mariusz B. jest ich 203, poniżej @bogdans przecież wspomniał że niepotrzebnie miałem tam powtórzenia przy generacji danych. Anyway, poprawiłem ten kod żeby ktoś się znów tak nie pomylił ;]