Find Kth Element which has at least one divisor < 50

To find the k'th number whose at least one prime divisor is less than 50.

Prerequisite
Inclusion-Exclusion Principle

Solution
we just need to count how many number having at least one prime divisor less than 50.

We are trying to solve this question for smaller constraints
To find the k'th number who has at least one prime divisor is less than 5.
only prime numbers : {2,3}

counting divisor till X
count_div = X/2 + X/3 - X/(2*3)

So basically we need to add divisor of each element and subtract divisor of both once as they are added twice(once with 2 and once with 3)

So this Idea can be extended to any number of primes using Inclusion-Exclusion Principle.

P = p1*p2*....*pn

if n is odd
count_div += X/P
else
count_div -= X/P

For more clarification see the code.


Problem Link




Ramesh Chandra