Znajdź Liczbę Główną w najszybszy sposób, na warunkach w opisie.

Na dole jest krótka dokumentacja jaką robiłem razem z kodem. Problem jest taki, że chociaż wszystko działa poprawnie, to przy bardzo dużych liczbach pętla trwa zdecydowanie za długo.
Generalnie, to musimy znaleźć pierwszą parę liczb, której odstęp wynosi "g". Liczby te muszą być pierwsze, zaczynając od "m" i kończąc na "n".
Mam nadzieję, że rozumiecie mój problem, który dotyczy głównie optymalizacji i refaktoryzacji kodu.
Wiem też, że kata nie na tym polega, ale nie mam pojęcia co z tym zrobić, wszelka pomoc bardzo przydatna :)

Steps in Primes (13.04)

Entry

I have to find the first pair with gained spacing in range of two next parameteres.

Data

• g (integer >= 2) which indicates the step we are looking for,

• m (integer >= 2) which gives the start of the search (m inclusive),

• n (integer >= m) which gives the end of the search (n inclusive)

Examples:

step(2, 5, 7) --> [5, 7] or (5, 7) or {5, 7} or "5 7"

step(2, 5, 5) --> nil or ... or [] in Ocaml or {0, 0} in C++

step(4, 130, 200) --> [163, 167] or (163, 167) or {163, 167}

Reference:

1. A "gap" is more restrictive: there must be no primes in between (101-107 is a "step" but not a "gap". Next kata will be about "gaps":-).

2. "step" vs "gap"

Ways

1. Go through parameters to get actual numbers
2. Filter Prime Numbers
3. Find a closest pair of prime numbers (with correct step between)
4. Refactor and Submit

Code (Unsolved yet)

def step(g, m, n):
   primes = []

   ##FILTER PRIMES##
   for x in range(m, n):
       if x > 1:
           # check for factors
           for i in range(2, x):
               if (x % i) == 0:
                   break
           else:
               primes.append(x)
   
   ##FIND A PAIR##
   y = 0
   print(primes)
   
   for x in range(0, len(primes)):
       i = 1
       while y != g:
           if i+x >= len(primes)-1:
               break
           y = primes[x+i] - primes[x]
           i += 1
       if y == g:
           return sorted([primes[x+i-1], primes[x]])
   return None

#EASY CHECK
x = step(4,130,200) #[163, 167]

#HARDCORE CHECK
#x = step(4,30000,100000) #[359, 367]
print(x)

Widzisz, że Masz złożoność kwadratową, dwie zagnieżdżone pętle; nie licz w ten sposób liczb pierwszych, tylko użyj sita:
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

@lion137: Pierwsza pętla służy do wyznaczenia cyfr z zakresu m do n i nie wiem czym miałbym zastąpić drugą, zagnieżdżoną pętlę. Na tym polega problem, że muszę teoretycznie sprawdzić wszystkie liczby z zakresu m, n, i stwierdzić, która jest liczbą pierwszą. Poczytam natomiast o złożoności kwadratowej, byłbym również wdzięczny o reprezentację myśli w formie kodu jeżeli nie mam racji.

@lion137: Co do sita, to myślałem, że ów zastosowałem, ale sam już pewny nie jestem i obejrzę sobie materiał na ten temat.

Jeszcze raz odnośnie algorytmów, aktualnie jestem w momencie, w którym jako programista nowicjusz zdajesz sobie sprawę, że algorytmy jednak warto poznać, a do samego kodu podchodzić dopiero po rozwiązaniu problemu. Myśl ta jest nadal rozwijana dopiero od paru dni i na razie poznałem wyszukiwanie binarne, a linearne, rekursywność i sortowanie selekcyjne. Gdybyś miał pomysł jakie jeszcze algorytmy są ważne to byłbym wdzięczny za to. Jeszcze na liście mam teraz sito i algorytm euklidesa.

Algorytmy to oddzielna sprawa, załóż watek, albo przejrzyj spisy treści popularnych podręczników ;-) Co do problemu, musisz sie pozbyć tej podwójnej pętli albo sitem, albo zastąpić ją jakąś efektywną metoda sprawdzająca, czy liczba jest pierwsza, https://en.wikipedia.org/wiki/Primality_test

@lion137: Ok, dzięki, spróbuję to zrobić sitem i jak się z tym uporam to zamykam wątek, na razie jeszcze potrzymam w razie moich kolejnym ciekawych pytań hah, natomiast raczej fakt, że upomniałeś mnie o to sito powinien mi wystarczyć. :)

Dobrze, że nie zamknąłem wątku, bo albo nie umiem implementować sita, albo nie daje on sobie tu rady. Jeżeli ktoś widzi błąd, to byłbym wdzięczny za poprawienie go również w kodzie, gdyż wydaje mi się, że nie znajdę rozwiązania.

def step(g, m, n):
    primes = []

    ##SIVE [NOT WORKING]##
    temp = [1 for x in range(n + 1)]
    for i in range(2, n + 1):
        for j in range(i + 1, n + 1):
            if j % i == 0:
                temp[j] = 0

    for i in range(2, len(temp)):
        if temp[i] == 1:
            primes.append(i)
    
    if m in primes:
        primes = primes[primes.index(m):]
    
    else:
        k = 1
        while m not in primes:
            if m+k in primes:
                primes = primes[primes.index(m+k):]
                break
            k+=1
            

    
    ##FIND A PAIR##
    y = 0
    
    for x in range(0, len(primes)):
        i = 1
        while y != g:
            if i+x >= len(primes)-1:
                break
            y = primes[x+i] - primes[x]
            i += 1
        if y == g:
            return sorted([primes[x+i-1], primes[x]])
    return None

#EASY CHECK
#x = step(4,130,200) #[163, 167]

#MEDIUM CHECK
x = step(4,30000,100000) #[30109, 30113]

#HARDCORE CHECK
#x = step(4,885795,985795) #[885889, 885893]

print(x)

Działające sito:

from itertools import repeat


def sqrt_int(n):
    "Integer square root (rounds down)."
    return int(n ** 0.5)


def sieve(n):
	N = n // 2 
	_sieve = [True] * N
	for i in range(3, sqrt_int(n) + 1, 2):
		if _sieve[i // 2]: 
			start = i ** 2 // 2
			_sieve[start::i] = repeat(False, len(range(start, N, i)))
	_list = [2] + [2*i+1 for i in range(1, N) if _sieve[i]]
	return _list

Task z gwiazdką, przerobić, żeby zwracało liczby pierwsze dla dowolnego przedziału, a nie, jak teraz, do, n.

@lion137: Jak wstawiłem to twoje i użyłem, to mi takie listy zaczęły dziwne wychodzić, zamiast się w to zagłębiać, mógłbyś pokazać jak wyglądałoby to w moim kodzie, tak żeby wychodziły dobre wyniki? Mam zarówno funkcję jak i odpowiedzi zapisane pod nazwami poziomów trudności, np.
x = step(4,30000,100000) #[30109, 30113] gdzie po "#" mamy poprawną odpowiedź.

Jak próbowałem inną formę sita implementować to działało na poziomie Easy, ale na dalszych to pętla nie wyrabiała. Sito też stosuje pętle, która sama w sobie wydaje się nie wyrabiać.

Co dokladnie oczekujesz, że będzie w primes przed FIND A PAIR?

@lion137: mają być liczby pierwsze z zakresu od parametru podanego m do drugiego n

druga część to znaleźć najbliższą parę dwóch liczb pierwszych, którą dzieli odstęp "g".

To przecież prosto:

def step(g, m, n):
    primes = [p for p in sieve(n + 1) if p >= m]
    #  finding a pair
    y = 0
    for x in range(0, len(primes)):
        i = 1
        while y != g:
            if i+x >= len(primes)-1:
                break
            y = primes[x+i] - primes[x]
            i += 1
        if y == g:
            return sorted([primes[x+i-1], primes[x]])

Sprawdzaj tylko nieparzyste liczby, jedyna parzysta liczba pierwsza to 2. Jak jest poza zakresem, to G musi być parzyste, inaczej j jedna nie będzie pierwsza (bo parzysta). Więc rozwiązań brak bez liczenia czegokolwiek.

Starałem się najprościej i najczytelniej

#sito Erastotenesa O(n log log n)
def sieve(m, n):
    primes, nums = [], [1, 1] + [0] * (n+1) # 0 i 1 nie sa pierwsze
    for i in range(2, int(n**0.5)+1):
        if nums[i] == 0:
            for k in range(i * i, n+1, i):
                nums[k] = 1
    return [p for p in range(m, n+1) if nums[p] == 0]

# metoda gasienicy, dwoch wskaznikow O(n)
def find_pair_primes(g, primes):
    beg = end = 0
    while end < len(primes):
        # znalezlismy g
        if primes[end] - primes[beg] == g:
            return primes[beg], primes[end]
        # za mala roznica, musimy zwiekszyc rozmiar gasienicy
        elif primes[end] - primes[beg] < g:
            end += 1
        # za duza roznica, musimy zmiejszyc rozmiar gasienicy
        else:
            beg += 1
    # jesli nie znalezlismy g zwracamy (-1, -1)
    return -1, -1

def main():
    g, m, n = map(int, input().split())
    print(find_pair_primes(g, sieve(m, n)))
    
main()

@Suchy702: Już wątek chyba porzucę, bo nie mogłem znaleźć rozwiązania, a codewars też na tym nie polega, że od kogoś wezmę, ale przejrzę twój kod, to dzięki i tak.
Problem z nim, żeby na codewars wrzucić to powinna być funkcja przyznana na początku zadania i musi zawsze zwracać wynik końcowy czyli return. (funkcja to convertFracts)
Gdybyś chciał przetestować swój kod na stronce, to kata miała nazwę Common Denominators za 5kyu. Jeszcze raz dzięki, zamykam wątek. :)