All Tracks Math Number Theory Basic Number Theory-2 Problem

D. Prime Counting
Tag(s):

Greedy Algorithms, Math, Sieve

Problem
Editorial
Analytics

Deepjoy is very much fond of prime numbers. He is fascinated by the fact that these numbers are divisible by only $$2$$ numbers ($$1$$ and the number itself).

His friends challenged him with a problem related to the prime numbers which he eventually cracked.

Now its your turn to solve the problem. Lets see whether you can solve it or not!

You are given $$N$$ intervals in the form of $$[l_i, r_i]$$ (for each valid $$i$$, where $$ 1 \le i \le N $$). Each interval contains contains all the integers $$x$$ satisfying the condition $$x \ge l_i, x \le r_i$$. Now find the intersection of all the intervals (integers common to all the intervals) and print the count of the number of primes within the common intersection interval.

 

Input: 

  • First line: A single integer $$ T $$ denoting the number of test cases
  • Each test case contains the following lines:
    • $$1st$$ line: $$N$$, the no. of intervals
    • $$N$$ lines follow giving the intervals in the form of $$l, r$$

Output:

Print the count of prime nos. lying in the common interval (of all the $$N$$ intervals). If there is no common interval among the $$N$$ intervals, print $$-1$$.

Constraints:

$$ 1 \le T \le 10 $$

$$ 1 \le N \le 10 $$

$$ 1 \le l_i \le r_i \le 10^9 $$

$$ 1 \le r_i-l_i \le 10^5$$

SAMPLE INPUT
2
2
2 10
5 19
2
2 3
6 100
SAMPLE OUTPUT
2
-1
Explanation

$$1st$$ test case:

The common interval is $$[5,10]$$. Now the prime nos. within this range are $$5,7$$. So the total prime nos. within this range is $$2$$. 

Time Limit: 0,3 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

?