VECTAR8 - Primal Fear

no tags 

Changu and Mangu are afraid of prime numbers, but they are not afraid of all prime numbers. They were afraid of only a special kind of prime numbers. They are afraid of the prime numbers (without the digit zero, they love all the primes which have digits 0 in them) that remain prime no matter how many of the leading digits are omitted. For example, they are afraid of 4632647 because it doesn't have the digit 0 and each of its truncations (632647, 32647, 2647, 647, 47, and 7) are primes.

You are given a simple task, given a number of N, find out the number of primes not greater that N, that changu and mangu are afraid of.


The first line contains T, the number of test cases. T lines follow, each containing a number N.


On each line print the number of primes not greater that N, that changu and mangu are afraid of.





T ≤ 10^5

1 ≤ N < 10^6

hide comments
omarwageeh: 2017-09-11 09:58:19

make sure you check that all the truncations of a prime that has no zeroes are prime as in the example.... 632647, 32647, 2647, 647, 47, and 7
Caused me 3 WA

nihal_magdy: 2017-08-18 11:48:23

@piyush can you see what is the wrong test i get with my code 19995055

rohit659: 2017-04-06 21:42:37


dwij28: 2016-10-07 23:40:01

A very nice problem. In fact all problems by @Piyush Kumar i.e the VECTAR series are very nice. :)

rainy jain : 2016-09-13 02:32:57

Last edit: 2016-09-13 09:21:17
sy_117: 2016-08-13 15:33:29

such a nice problem !!! A lot of optimization needed to avoid TLE . :)

crazy97: 2016-07-25 20:53:11

Last edit: 2016-07-30 08:44:42
sachintanwar: 2016-07-08 09:30:46

I used this code and getting TLE continuously
<code deleted>

Re: Please don't post any codes here. Use Forum.
Brute Force won't pass. Think of other ways. Good luck.

Last edit: 2016-07-08 16:27:57
sumit kumar singh: 2016-07-07 11:44:03

cin/cout caused me 2 TLE .. :(

Re: cin/cout will not cause you TLE if you have an efficient solution. My slowest solution uses cin/cout and passes the time limit comfortably.

Last edit: 2016-07-07 12:33:56
akshayvenkat: 2016-07-07 08:26:26

@piyush please check my submission. is this way of solving ethically acceptable? ID:17236762

Re: Yeah, you can do this any time :) But for a challenge, you can try out other ways :)!

Last edit: 2016-07-07 08:57:53

Added by:Piyush Kumar
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY