Les nombres qui ne sont pas divisibles

Question

On vous donne un entier positif N. Votre tâche consiste à trouver le nombre d'entiers positifs K ≤ N tel que K n'est divisible par aucun nombre parmi l'ensemble {2,3,4,5,6,7,8,9,10}.

Je pensais à tous les nombres premiers mais ça ne donne pas la bonne réponse.

Étonnamment, la réponse est très simple.

#include <iostream>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--) {
        long long n;
        cin>>n;
        long long ans = (n/2+n/3+n/5+n/7)-(n/6+n/10+n/14+n/15+n/21+n/35)+(n/30+n/42+n/70+n/105)-(n/210);
        cout<<n - ans<<endl;
    }
    return 0;
}

Mais je n'ai pas compris cet algo. Quelqu'un peut-il m'expliquer cet algo ?

Answer 1

Les nombres premiers de l'ensemble sont 2, 3 ,5 et 7. En utilisant ceux-ci, nous comptons :

how many numbers up to N are divisible by 2, 3, 5 and 7

mais on a surcompté les nombres qui sont divisibles par les deux :

2,3 = 6
2,5 = 10
2,7 = 14
etc.

mais on a sur-soustrait tous les nombres divisibles par les trois :

2,3,5 = 30
2,3,7 = 42
etc.

etc...

Ce principe combinatoire est appelé inclusion-exclusion .

Ce qui reste après ce processus n'était pas divisible par ces nombres premiers. (Notez que si un nombre n'est pas divisible par 2, il n'est pas divisible par 4, 6, 8 et 10 ; idem pour 3 et 9).

Answer 2

D'abord, comptez les nombres qui ne sont pas divisibles par les nombres premiers de l'ensemble.

• n/2 des nombres ne sont pas divisibles par 2.
• n/3 des nombres ne sont pas divisibles par 3.
• etc.

Cependant, certains nombres ont été comptés deux fois. Les nombres non divisibles par 6 ne sont ni divisibles par 2 ni par 3, on les soustrait donc du total.

Des nombres comme 30 ont été comptés trois fois dans la première phase (en tant que multiple de 2, 3 et 5), mais elle a été prise en compte dans le calcul de l'impact de l'opération. trois fois dans la deuxième phase (en tant que multiple de 6, 10 et 15). Nous devons donc les ajouter dans à nouveau pour une contribution nette de 1.

Ainsi, chaque expression entre parenthèses dans la réponse finale représente soit le comptage des nombres qui ne sont pas divisibles par un nombre de l'ensemble, soit la compensation d'un sur ou sous-comptage précédent.

Answer 3

Il existe une solution non récursive.

int N = ....; 
int const primes[4] = {2,3,5,7};
int result = 0;
for(int i = 0; i < 16; ++i)// 16 = 2^4
{ 
    int p = 1, s = 1; // s = (-1)^bits(i).
    for(int j = 0; j < 4; ++j)
        if ( ( i >> j ) & 1 ) 
            p *= primes[j], s *= -1;

    result += (N / p) * s; 
}