Algorithm
Problem link- https://www.spoj.com/problems/VECTAR8/
VECTAR8 - Primal Fear
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.
Input
The first line contains T, the number of test cases. T lines follow, each containing a number N.
Output
On each line print the number of primes not greater that N, that changu and mangu are afraid of.
Example
Input: 3 2 3 4 Output: 1 2 2
Constraints
T ≤ 10^5
1 ≤ N < 10^6
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p<<1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e6+5;
int isPrime[MAXN];
void sieve(){
isPrime[0] = isPrime[1] = 1;
for(int i = 2;i*i <= 1000000; i++){
if(isPrime[i] == 0){
if(i*1LL*i <= 1000000){
for(int j = i*i;j <= 1000000; j += i)
isPrime[j] = 1;
}
}
}
}
int cnt[MAXN];
bool toBeAfraid(ll num){
ll dig = 0;
ll tmpNum = num;
while(num > 0){
if(num%10 == 0)
return false;
dig++;
num /= 10;
}
ll div = exp(10LL, dig-1);
num = tmpNum;
while(num > 0){
num %= div;
div /= 10;
if((num != 0 && isPrime[num] == 1))
return false;
}
return true;
}
void precal(){
for(int i = 2;i <= 1000000; i++){
cnt[i] = cnt[i-1];
if(isPrime[i] == 0){
if(toBeAfraid(i))
cnt[i]++;
}
}
}
int main(){
io;
sieve();
precal();
int t;
cin >> t;
while(t--){
int n;
cin >> n;
cout << cnt[n] << endl;
}
return 0;
}Input
2
3
4
Output
2
2
Demonstration
SPOJ Solution-Primal Fear-Solution in C, C++, Java, Python