Number of numbers between 1 and n which are divisible by primes less than 20

#1

https://hastebin.com/aporifisiq.cpp

please tell whether it passes all test cases or not . is it the correct approach??

#2

@gulatigarvita08 no one divides the prime number except the number itself and 1, so ans for any n should be 2 . what are you trying to say? can you give an example.
also your code gives o/p 9 for i/p 10 which is wrong

1 Like
#3

find out number of numbers between 1 and n which are divisible by any of the primes less than 20 .
first line consists of number of test cases . then t lines follow which consists of number n for each test case.

sample input
5
5
10
12
15
18

sample output
4
9
11
14
17

#4

@gulatigarvita08 got your question wait let me check for some test cases

1 Like
#5

@gulatigarvita08 its giving right for cases i tried ( compared it with the brute force soln and answer matches) , so it seems correct :smiley:
if cleared dont forget to hit like and mark resolved

1 Like
#6

can you please explain me its time complexity…

#7

@gulatigarvita08 its approx o(1e6+txn) as sieve function takes approx 1e6 time and main txn

1 Like
#8

so finally o(txn) ??

#9

@gulatigarvita08 no max(txn,1e6)

1 Like
#10

actually i don’t have much idea on complexity …what’s o(1e6) ?? is it constant

#11

1e6 = 1000000 @gulatigarvita08

1 Like
#12

o(1e6) ?? am not asking 1e6

#13

consider a loop which runs from i=0, i<var ; i++ where var=1e6 . so complexity o(var) which is also o(1e6)

1 Like
#14

okay okay …thank you so much…

can there be more optimized approach for the same

#15

@gulatigarvita08 no yours good

1 Like
#16

okay…thank you so much…

#17

np garvita just mark it as resolved :smiley:

1 Like