Find out the number of numbers between 1 and n which are divisible by any of the prime numbers less than 20

S18LP0029 · September 13, 2019, 4:22pm

passes sample case but fails in other please tell problem

Robin_rst · September 19, 2019, 11:54am

Your are only subtracting the pairs which have twice counted but this is not true if you have more than 3 primes which divides the same number. Let suppose for 30, counts will be like -:
2 - (30/2)= 15;
3 - (30/3)=10;
5 - (30/5)= 6;
So total count will be 31 but the number divisible by (2,3), (2,5), (3,5) are counted twice and if you remove those counts then the number with (2,3,5) will be subtracted too, so you have to add that too.
Use the Inclusion-Exclusion Principle general formula.
AUBUC … = odd(single element) - (pairs) + odd(triplets) - even(quadraples …so on.

You can see my implementation for better understanding.

github.com

robinrst/NumberTheory/blob/master/NotSoEasyMath.cpp

#include "bits/stdc++.h"

using namespace std;

#define  f first
#define  lgn 25
#define  endl '\n'
#define  sc second
#define  N (int)2e5+5
#define  sz(x) x.size()
#define  int long long int
#define  ld long double
#define  vi vector<int>
#define  vs vector<string>
#define  vc vector<char>
#define  mii map<int,int>
#define  pii pair<int,int>
#define  vpii vector<pii>
#define  test(x) while(x--)
#define  pb push_back

This file has been truncated. show original

Robin_rst · September 25, 2019, 10:20am

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.