Znajdowanie liczb od a do b nie podzielnych przez x do y

Question

To jest problem, nad którym się zastanawiam od dłuższego czasu.

Jaki jest najszybszy sposób na znalezienie wszystkich liczb od a do b, które nie są podzielne przez żadną liczbę od x do y?

Rozważ to:

chcę znaleźć wszystkie liczby od 1 do 10, które nie są podzielne przez 2 do 5. Proces ten będzie bardzo powolny gdybym gdzie używać podejścia liniowego; Jak to:

result = [] 
a = 1 
b = 10 
x = 2 
y = 5 
for i in range(a,b): 
    t = False 
    for j in range(x,y): 
     if i%j==0: 
      t = True 
      break 
    if t is False: 
     result.append(i) 
return result 

Czy ktoś wie o wszelkich innych metod robi to mniej czasu obliczeń niż rozwiązanie liniowego?

Jeśli nie, ktoś może zobaczyć, jak to potęga być wykonane szybciej, jak ja w tej chwili pusty ...

poważaniem John

[EDIT]

Zakres liczby wynosi od 0 do> 1, e + 100

Dotyczy to opcji a, b, x oraz y

Answer 1

Należy tylko sprawdzić wartości podstawowe w zakresie możliwych dzielników - na przykład, jeśli wartość nie jest podzielna przez 2, nie będzie podzielna przez dowolną wielokrotność 2; podobnie dla każdej innej liczby pierwszej i najwyższej. Tak więc w twoim przykładzie możesz sprawdzić 2, 3, 5 - nie musisz sprawdzać 4, ponieważ wszystko podzielne przez 4 musi być podzielne przez 2. Dlatego szybszym podejściem byłoby obliczenie liczb pierwszych w dowolnym zakresie, który cię interesuje, a następnie po prostu obliczyć, które wartości dzielą.

Kolejnym przyspieszeniem jest dodanie każdej wartości z zakresu, który Cię interesuje, do set: gdy okaże się, że jest podzielna przez liczbę z twojego zakresu, usuń ją z zestawu. Powinieneś wtedy testować tylko liczby pozostające w zestawie - to zatrzyma testowanie liczb kilka razy.

Jeśli połączymy te dwa podejścia, zobaczymy, że możemy utworzyć set wszystkich wartości (więc w przykładzie, zestaw ze wszystkimi wartościami od 1 do 10) i po prostu usunąć wielokrotności każdego primera w drugim zakresie z tego zestawu.

Edytuj: Jak zauważył Patashu, nie będzie to działało, jeśli podstawowa dzieląca daną wartość nie jest w zbiorze. Aby to naprawić, możemy zastosować podobny algorytm do powyższego: stwórz set z wartościami [a, b], dla każdej wartości w set, usuń wszystkie jej wielokrotności. Tak więc dla przykładu podanego poniżej w komentarzach (z [3, 6]) zaczynamy od 3 i usuwamy jego wielokrotności w zestawie - czyli 6. Dlatego pozostałe wartości, które musimy przetestować, to: [3, 4, 5], czego chcemy w tym przypadku.

Edit2: Oto naprawdę włamał się, że brzydko realizacja nie została zoptymalizowana i ma straszne nazwy zmiennych:

def find_non_factors(): 
    a = 1 
    b = 1000000 
    x = 200 
    y = 1000 

    z = [True for p in range(x, y+1)] 
    for k, i in enumerate(z): 
     if i: 
      k += x 
      n = 2 
      while n * k < y + 1: 
       z[(n*k) - x] = False 
       n += 1 

    k = {p for p in range(a, b+1)} 

    for p, v in enumerate(z): 
     if v: 
      t = p + x 
      n = 1 
      while n * t < (b + 1): 
       if (n * t) in k: 
        k.remove(n * t) 
       n += 1 

    return k 

Spróbuj oryginalne wykonanie z tymi numerami. Zajmuje to> 1 minutę na moim komputerze. Ta implementacja zajmuje mniej niż 2 sekundy.

Answer 2

Ostrzeganie przed optymalizacją: nie należy wstępnie optymalizować. Za każdym razem, gdy próbujesz zoptymalizować kod, profiluj go, aby zapewnić jego optymalizację, i zoptymalizuj profil optymalizacyjny dla tego samego rodzaju danych, które zamierzasz zoptymalizować, aby potwierdzić, że jest to przyspieszenie. Prawie cały kod nie wymaga optymalizacji, aby podać poprawną odpowiedź.

Jeśli optymalizacji dla małych X Y i duży a-b:

utworzyć tablicę o długości, która jest najmniejsza wspólna wielokrotność spośród wszystkich x, x + 1, x + 2 ... y. Na przykład dla 2, 3, 4, 5 będzie to 60, a nie 120.

Teraz wypełnij tę tablicę bajtami - na początku false dla każdej komórki, następnie dla każdej liczby w xy zapełnij wszystkie wpisy w tablicy, są wielokrotnościami tej liczby z wartością true.

Teraz dla każdej liczby w a-b, indeksuj do tablicy długości modulo i jeśli jest to prawda, pomiń jeszcze, jeśli jest to fałsz, zwróć.

Możesz zrobić to trochę szybciej, usuwając z ciebie liczby czynników x do y, które są rozszerzonymi czynnikami pierwszeństwa o ścisłe nadzbiory z dodatkami innych czynników o priorytetach. Przez co mam na myśli - jeśli masz 2, 3, 4, 5, 4 to 2 * 2 ścisły nadzbiór 2, więc możesz go usunąć, a teraz nasza długość tablicy wynosi tylko 30. Dla czegoś takiego jak 3, 4, 5, 6 jednak 4 to 2 * 2, a 6 to 3 * 2 - 6 to nadzbiór 3, więc go usuwamy, ale 4 nie jest nadzbiorem wszystkiego, więc trzymamy go. LCM to 3 * 2 * 2 * 5 = 60 Robiąc takie rzeczy przyspieszałoby samo w sobie dla dużych ab i nie musisz iść w kierunku tablicy, jeśli to wszystko, czego potrzebujesz.

Pamiętaj też, że jeśli nie zamierzasz używać całego wyniku funkcji za każdym razem - np. Być może interesujesz się tylko najniższą wartością - zapisz ją jako generator, a nie jako funkcja. W ten sposób możesz zadzwonić, dopóki nie masz wystarczającej liczby, a następnie przestać, oszczędzając czas.