Brauchen Sie Hilfe bei der Lösung der folgenden effizient in Bezug auf die zeitliche Komplexität

Question

Ich versuche, das Problem für die letzten zwei Tage zu lösen. Ich kann mir keine andere Lösung als die rohe Gewalt vorstellen. Irgendwelche Arten von Hinweisen oder Referenzen werden geschätzt. TIA.

„Gegeben N verschiedenen Primzahlen d.h p1, p2, ..., pN und ein Intervall [L,R]. Berechnen der Anzahl von ganzen Zahlen in diesem Intervall, das von mindestens einem der angegebenen Primzahlen teilbar sind.“

N sehr klein ist (1 < = N < = 10) und L ist R sehr groß (1 < = L < = R < = 10^10)

Answer 1

Erste Anmerkung, es ist einfacher, das Problem zu beschränken, und ignorieren Sie die untere Grenze (dh: behandeln L = 1). Wenn wir teilbare Zahlen durch die Primzahlen zählen < = N für jede N, können wir zählen sie auch auf einem Intervall, durch die Anzahl der Zahlen subtrahieren < = L-1 von der Zählung < = R.

Gegeben eine beliebige Anzahl x, die Anzahl der Zahlen < = R teilbar durch x ist Boden (R/x).

Jetzt können wir die inclusion-exclusion principle anwenden, um das Ergebnis zu erhalten. Zuerst zeige ich die Ergebnisse von Hand für 3 Primzahlen p1, p2 und p3 und gebe dann das allgemeine Ergebnis an.

Die Zählung von Zahlen < = R teilbar durch p1, p2 oder p3 ist:

R/p1 + R/p2 + R/p3 
- R/(p1p2) - R/(p1p3) - R/(p2p3) 
+ R/(p1p2p3) 

(Hier wird angenommen / Integer-Division werden Abrundungs).

Der allgemeine Fall ist wie folgt:

sum((-1)^(|S|+1) * R/prod(S) for S a non-empty subset of {p1, p2, .., pN}). 

Hier S Bereiche über alle Teilmengen Ihrer Primzahlen, prod(S) ist das Produkt der Primzahlen in der Teilmenge und die anfängliche Laufzeit variiert zwischen -1 und +1 abhängig von der Größe der Teilmenge.

Für Ihr Problem, N < = 10, so gibt es 1023 nicht leere Subsets, die eine kleine Anzahl von Dingen durchlaufen.

Hier einige Beispiel Python-Code: nur abhängig von der Anzahl der Primzahlen

from itertools import * 

def powerset(iterable): 
    s = list(iterable) 
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) 

def prod(ns): 
    r = 1 
    for n in ns: 
     r *= n 
    return r 

def divs(primes, N): 
    r = 0 
    for S in powerset(primes): 
     if not S: continue 
     sign = 1 if len(S) % 2 else -1 
     r += sign * (N // prod(S)) 
    return r 

def divs_in_range(primes, L, R): 
    return divs(primes, R) - divs(primes, L-1) 

Beachten Sie, dass die Laufzeit dieses Codes mehr oder weniger ist, und nicht so sehr auf die Größen L und R.

Answer 2

Unter der Annahme, n die Intervallgröße ist und N ist const.

Für jede Primzahl p sollten in dem Intervall, das durch die Primzahl teilbar ist, ungefähr (R-L)/p Zahlen sein.

Finden der ersten Zahl, die im Intervall durch p teilbar ist: L '= L + (p - L% p).

Jetzt, wenn L '> R, gibt es keine; Ansonsten gibt es 1 + Boden ((R-L ')/p).

Beispiel: 3, [10, 20]:

L‘= 10 + 3 - 10% 3 = 12.

Zahlen durch 3 teilbar im Intervall: 1 + floor ((20 - 12)/3) = 3

Hinweis: Bisher haben wir nicht die Tatsache verwendet, dass p1..pN Primzahlen sind.

Das verbleibende Problem scheint zu sein: Wie kann man vermeiden, eine Zahl zu zählen, die mehrmals durch mehrere Primzahlen teilbar ist? Beispiel: Angenommen, wir haben 3,5 und [10, 20], müssen wir vermeiden, zweimal 15 zu zählen ...

Vielleicht können wir die Teilbarkeit nur mit (p1 * p2) usw. unter Verwendung des obigen Zählalgorithmus zählen die Summe entsprechend reduzieren? Wenn N ist const, sollte dies immer const time sein. Da p1 ... pN Primzahlen sind, müssen alle ihre Produkte verschieden sein (da jede Zahl nicht mehr als eine Primfaktorzerlegung haben kann).