CNTPRIME  Counting Primes
Tortoise and Achilles are playing the Counting the Primes game. Achilles will give Tortoise some numbers, and some intervals, and then Tortoise needs to count the primes on those intervals. It is an easy game, but Tortoise is doing the counting slowly. Achilles is pissed off, so he has given you the task as you are a good programmer. For a twist, he has changed the game a little bit, that is he will give some intervals for counting the prime as well as he will give some intervals to change the numbers in that interval.
You are given an array of n elements. After that you will be given M commands. They are 
 0 x y v  you have to change all numbers in the range of x to y (inclusive) to v, where x and y are two indexes of the array.
 1 x y  output a line containing a single integer which is the number of primes between x and y (inclusive).
The array is indexed from 1 to n.
Input:
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case contains two integers n (1 ≤ n ≤ 10^{4}) and q (1 ≤ q ≤ 2*10^{4}). Then next line, you will be given N integers. After that each of the next q lines will contain a task in one of the following form:
 0 x y v (1 ≤ x ≤ y ≤ n, 2 ≤ v ≤ 10^{6})
 1 x y (1 ≤ x ≤ y ≤ n)
And the numbers will be in range of [2, 10^{6}].
Output:
For each case, print the case number first. Then for each query '1 x y', print the number of primes between x and y [inclusively].
Sample Input 
Output for Sample Input 
1 5 3 78 2 13 12 3 1 1 2 0 4 4 5 1 1 5 
Case 1: 1 4 
Note:
 Use Faster IO like scanf,printf
 A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first prime numbers are 2,3,5,7,11....2,3,5,7,11,…
hide comments
shiv2111:
20180114 17:04:37
cakewalk st+lazy 

siddharth_0196:
20170610 13:13:48
Changing array size from 10^5 to 4*10^4 changed TLE to AC! _ 

lord_poseidon:
20170602 08:33:57
AC in one go 

ingeniosus:
20170126 20:50:39
Can't figure out the bug in my code!!!


RISHABH THAKUR:
20160801 22:07:39
be aware of printing Case 1: cost me 3 WAs


kiwi1995:
20160707 12:56:15
take care of output format...costs me 3 WA's because i missed ":" at the end...


xinnix:
20160702 17:01:53
Can't understand the test case given. How is the output 4? 

sciencepal:
20160618 16:05:58
Time limit is really strict for this one. 

naruto09:
20160326 00:46:00
silly mistake.._ 

bound_less:
20160308 18:48:32
Note that there is a \n after anything you print. 
Added by:  Faiyaz 
Date:  20121216 
Time limit:  0.234s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 