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 starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 104) and q (1 ≤ q ≤ 2*104). 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 ≤ 106)
  • 1 x y (1 ≤ x ≤ y ≤ n)

And the numbers will be in range of [2, 106].


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


5 3

78 2 13 12 3

1 1 2

0 4 4 5

1 1 5

Case 1:




  • 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
sriankit: 2013-12-19 16:11:16

Lazy propagation gives TLE in java.. :(

(Tjandra Satria Gunawan)(曾毅昆): 2013-12-19 16:11:16

@akb: I didn't use segment tree to solve this problem, so I don't know. But, I know that the constraints is correct (no case with n>10^4).

akb: 2013-12-19 16:11:16

someone please explain me why segtree size 6*10^4 is giving WA but 10^5 is AC.

Re: Maybe because of the way you are building the tree. My code passes with 4*10^4 tree size. :)

Last edit: 2013-02-26 08:17:23
mehmetin: 2013-12-19 16:11:16

Lazy Prop. with optimized IO passes

Last edit: 2012-12-23 22:59:23
(Tjandra Satria Gunawan)(曾毅昆): 2013-12-19 16:11:16

@Mehmet Inal: You need an efficient data structure to solve this problem.

mehmetin: 2013-12-19 16:11:16

Should we use lazy propagation?

Last edit: 2012-12-23 13:26:44
npsabari: 2013-12-19 16:11:16

Segment Tree with 3*10^4 nodes gave WA. but with 4*10^4 nodes gave AC. But as n <= 10^4 the first one should have got AC.. So be careful while choosing the array sizes

Rahul Shah: 2013-12-19 16:11:16

can anyone provide some tricky test code is giving right for almost all inputs..

Last edit: 2012-12-21 10:55:24
Aditya Pande: 2013-12-19 16:11:16

got TLE with my first attempt
the prime part is hardly a problem but the query part is.

Last edit: 2012-12-22 04:12:44
(Tjandra Satria Gunawan)(曾毅昆): 2013-12-19 16:11:16

ok, done... 2.2M of memory and 0.3s time... this is my best :-D

Added by:Faiyaz
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem