All Tracks Math Number Theory Basic Number Theory-2 Problem

Love for Numbers
Tag(s):

Mathematics, Prefix, Sieve

Problem
Editorial
Analytics

Kefa is very much fond of prime numbers. In order to test her fondness with these special set of numbers (prime numbers), one of her friends Alexa gave her a task to solve.

The problem which she gave is stated below.

Let $$F(x)$$ and $$G(x)$$ be two functions, such that $$F(x)$$ gives the largest prime factor of $$x$$ whereas $$G(x)$$ gives the smallest prime factor of $$x$$.

Let $$S = \sum_{i=l}^{r} F(i) - \sum_{i=l}^{r} G(i)$$, where $$l$$ and $$r$$ are two integers satisfying the condition $$2 \le l \le r$$.

You have to find the value of $$S$$.

When Alexa challenged Kefa with this problem, she absolutely nailed it! (I mean to say solved it). Now it's your turn. Can you solve it?

Note:

  • The functions $$F(x)$$ and $$G(x)$$ are defined for all values of $$x\ge2$$
  • Use Fast I/O

Scoring:

$$Score = max(0,m)$$, where $$m=(1000-$$number of characters in code$$)/10$$

Input:

  • First line: A single integer $$ T $$ denoting the number of test cases
  • Each test case contains two integers $$l$$ and $$r$$

Output:

Print the value of $$S$$ in a new single line for each test case.

Constraints:

$$ 1 \le T \le 10^6 $$

$$ 2 \le l \le r \le 10^6 $$

SAMPLE INPUT
2
3 7
15 17
SAMPLE OUTPUT
1
2
Explanation

Test case 1:

$$F(3) = 3, G(3) = 3$$

$$F(4) = 2, G(4) = 2$$

$$F(5) = 5, G(5) = 5$$

$$F(6) = 3, G(6) = 2$$

$$F(7) = 7, G(7) = 7$$

So, $$S = \sum_{i=3}^{7} F(i) - \sum_{i=3}^{7} G(i)$$ = $$(3+2+5+3+7) - (3+2+5+2+7) = 1$$

Test case 2:

$$F(15) = 5, G(15) = 3$$

$$F(16) = 2, G(16) = 2$$

$$F(17) = 17, G(17) = 17$$

So, $$S = \sum_{i=15}^{17} F(i) - \sum_{i=15}^{17} G(i)$$ = $$(5+2+17) - (3+2+17) = 2$$

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Уведомления
View All Notifications

?