Any Hint to solve : Number of numbers between 1 and n which are divisible by any of the prime numbers less than 20

#1

Hi,

I am stuck in solving this problem :

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

If N= 5 then the number of numbers are: 4
If N= 10 then the number of numbers are: 11

Any hint to start this, would be reallt helpful.

Thanks,
Pardeep.

#2

For starters, if N = 10, the numbers that are divisible by any of the prime numbers upto 20 are 2, 3, 4, 5, 6, 7, 8, 9, 10. So answer for N = 10 will be 9.

#3

Hi Abhishek,

I’d a brute force on this problem : https://ide.codingblocks.com/#/s/15041

Any idea how to improve on it?

Thanks

#4

Well here’s something :
Number of numbers in the range [X, Y] divisible by Z is

(Y/Z) - (X/Z) , if X%Z != 0
(Y/Z) - (X/Z) + 1 , if X%Z == 0

#5

Using Above formula, I can now able to calculate on O(N). But there’s a little bug in inclusion-exclusion of numbers may be.

This code is running for some 1-2 test cases. I am unable to rectify it. Please check.

Thanks.

#6
  1. It runs in O(1) not O(N) as O(N) will give TLE.
  2. You’ll have to modify the code. It counts the same number more than once.
    Say N = 10 :
    case 2 : 2, 4, 6, 8, 10
    case 3 : 3, 6, 9
    case 5 : 5, 10
    case 7 : 7

So, you see it’ll output 5+3+2+1 = 11, because 6 and 10 are counted twice. So what you need to do is count only those numbers which are not already considered.

#7

Hi,

I tried exclusion of number trick to do it. Now the total complexity is :

O(Prime_Numbers_Less_Than_N)

I ran it for all test case mentioned on coding blocks. Please check if I can improve on it further.

Thanks for replying.

#8

Your code isn’t correct. For N = 100, it gives 99 implying there are no prime numbers between 20 and 100 :smiley:
Approach this way :
In order to exclude 6 and 10 in the example I gave earlier, let the number of numbers divisible by 2 be c1 and that of 3 be c2. Now find the number of numbers that are divisible by 2*3 i.e. 6 (say c3) and put c1 + c2 - c3 in the final result. This was just for 2 and 3, you need to do this for the whole array of {2, 3, 5, 7, 11, 13, 17, 19}.

1 Like
#9

what is wrong in this code…i have used inclusion exclusion principle but it fails in 1 test case…

Code Link