CNTPRIME - Counting Primes

## 题目描述 给你一个 $n$ 个数的数组和 $m$ 个操作： - $0\ x\ y\ v$ 将 $x$ 到 $y$ 之间的所有数改成 $v$。 - $1\ x\ y$ 求 $x$ 到 $y$ 之间的质数个数。 数组下标为 $1$ 到 $n$。 ## 输入格式 第一行是一个整数 $T$，表示数据组数。 每组数据包含两个整数 $n$，$q$。 下一行是 $n$ 个整数表示数组 $a_i$。接下来的 $q$ 行，每行包含一个操作。形如： - $0\ x\ y\ v$ - $1\ x\ y$ $1 \le n \le {10}^4$，$1 \le q \le 2 \times {10}^4$，$2 \le x,y,v,a_i \le 10^6$ ## 输出格式 对于每组数据，先输出数据编号。然后对于每一个 $1\ x\ y$ 的询问，输出 $x$ 到 $y$ 之间的质数个数。 ## 提示 - 使用较快的输入输出方式，如 `scanf` 和 `printf`。 - 一个质数是一个除了 $1$ 和它本身意外没有其他正因数的大于 $1$ 的自然数。前几个质数是 $2,3,5,7,11...$

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 (, denoting the number of test cases.** Each case contains two integers **n (1 and **q (1 **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** - **1 x y (1** 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,…