You are not logged in. Please login at www.codechef.com to post your questions!

×

# How to approach this kind of number theory based problems?

 2 Milly and the Magic Numbers Milly likes to solve problems very much. Today she is solving a problem in which she has N, L and R and she has to find out the total count of Magic Numbers in [L, R] . Magic Numbers are the numbers which are divisible by at least one prime number in [1, N] . Being a beginner in programming, this one seems too hard for her to solve. So, she is asking you for her help, so your task is to solve this problem. Input First line of the input will have a integer T(number of test cases). Then each of the next T lines will contain 3 space separated integers: N, L and R. Output For each test case, print a single line having the count of Magic Numbers in [L, R]. Constraints 1 ≤ T ≤ 10 2 ≤ N ≤ 50 1 ≤ L ≤ R ≤ 1018 Sample Input 2 5 1 10 10 10 20 Sample Ouput 8 7 asked 05 Dec '16, 15:11 1★arpit728 683●17●65 accept rate: 10%

 2 @arpit728 It can be easily solved, if you know that the number of multiples of any number(say x) occurs upto certain number(say n) is equal to the $floor(n/x)$ (example: number of multiples of 4 upto 42 is $floor(42/4)=10$). In this question we can calculate number of multiples (between L and R) of each prime number less than N one by one. But this will include some numbers multiple time (example: for n=6, L=1 and R=32, 30 will be counted three times as multiple of 2, 3 and 5.), so we need to subtract that multiples of numbers formed by multiplying prime numbers two at a time. In above example, those numbers will be $2*3=6$, $2*5=10$ and $3*5=15$, but this will remove 30 three times so we need to add the count of multiples formed by multiplying primes taken three at a time (i.e., $2*3*5=30$). So, it can be generalized as: total count = $\sum$(count of multiples of primes taken one at a time) - $\sum$(count of multiples of product of prime taken two at a time) + .... $\sum$(count of multiples of product of all prime numbers) Example: N=6,L=1 and R=31; Let, count(x) = number of multiples of prime number x; So, total = (count(2) + count(3) + count(5)) - ((count($2*3$) + count($3*5$) + count($2*5$)) + ((count($2*3*5$));Final answer will be number of multiples till R - number of multiples till L, but in this example as L is 1 so we don't need to calculate seperately for L. count(2) = $floor(31/2)$ = 15 (2,4,6,8,10,12,14,16,18,20,22,24,26,28,30) count(3) = $floor(31/3)$ = 10 (3,6,9,12,15,18,21,24,27,30) count(5) = $floor(31/5)$ = 6 (5,10,15,20,25,30) count($2*3$) = $floor(31/6)$ = 5 (6,12,18,24,30) count($3*5$) = $floor(31/15)$ = 2 (15,30) count($2*5$) = $floor(31/10)$ = 3 (10,20,30) count($2*3*5$) = $floor(31/30)$ = 1 (30) total = (15+10+6) - (5+2+3) + (1) = 22 answered 05 Dec '16, 15:54 5★srd091 1.6k●1●11 accept rate: 42% Please explain the subtraction logic in more details. How the elements that are being counted multiple times is taken care of. (05 Dec '16, 22:34) arpit7281★ @arpit728 I've added an example to clear the logic. (06 Dec '16, 00:44) srd0915★ @arpit728 If you feel your question has been answered, mark it as accepted. (06 Dec '16, 00:46) srd0915★
 0 You can apply a sieve solution... 1. iterate from 2 to n   1. now mark all its multiples   2. add this marked element into a set 2. In the set now find all the marked elements between l and r Complexity:- O(nlog(n)) for marking the multiples and O(n) for counting... answered 05 Dec '16, 17:54 21●2 accept rate: 0%
 -2 Hey guys, check my website: http://codingeek.org/ answered 06 Dec '16, 02:56 0★ddacot -1 accept rate: 0%
 -2 Where do you get the 31/2 uhh, mate? answered 06 Dec '16, 10:46 32 accept rate: 8% @banghasan I've taken the value of R as 31 in the example. (06 Dec '16, 10:55) srd0915★
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,657
×631
×301
×199
×48

question asked: 05 Dec '16, 15:11

question was seen: 1,228 times

last updated: 06 Dec '16, 10:55