Étant donné les nombres L et R très grands (10^18), comment trouver le nombre de nombres entre L et R de sorte que les nombres aient au moins un premier facteurs de 1 à N.compter les nombres entre L et R qui ont au moins un facteur premier compris entre 1 et 50
note: N peut être à MAX 50
Je vais esquisser une méthode, ne fonctionne pas, il en détail.
Si R-L est très petit, il est probablement préférable de l'essayer un par un.
Sinon, utilisez le inclusion exclusion principle: Pour des raisons d'explication je considère simplement les nombres premiers 2,3, et 5. Déterminez combien de nombres peuvent être divisés par 2, 3, 5 (ie l'un des nombres premiers), 6, 10, 15 (c'est-à-dire deux des nombres premiers) et 30 (c'est-à-dire les trois nombres premiers). Pour un diviseur k c'est approximativement (R-L)/k, en tenant compte des conditions de frontière, nous pouvons obtenir le compte exact. Appelez le compte respectif c (k).
Maintenant, le nombre total de nombres divisibles par au moins un premier est:
c(2)+c(3)+c(5)-c(6)-c(10)-c(15)+c(30)
peut vous donner un exemple en plus petit nombre? – yd1
Quelle taille peut être N? Est-ce que L et R devraient être proches les uns des autres? –
@MarkDickinson 2 <= N <= 50 – smartsn123