VECTAR8--Help me with this problem from spoj

help
,
1

problem link–SPOJ.com - Problem VECTAR8

I have use the sieve algo to check for prime and composite but I am not able to crack the condition.

2

Can you share your submission (code)?

3

bro as I have mentioned, I have not completely solved the question,I have just used the sieve algo for prime

4

My Solution Link

5

Constraints are
T\le 10^5
1 \le N < 10^6
You are calculating the Answer for each test case everytime, which takes O(N) time per test case.
Instead just save pre-compute the answer for all values of N and then answer each testcase in O(1).

6

bro I have solved the sieve once,and using it for each test case.pls Have a look again

7

Yes, but this part

int count=0;
    for(int i=0;i<=n;i++)
    {
        if(prime[i]==1)
        {
            if(i%10!=0)
            count++;
        }
    }
    cout<<count<<"\n";

Instead of this,
maybe do this before testcase loop:

vector<int> count(n+1,0);
count[0] = 0;
 for(int i=1;i<=n;i++)
    {
        if(prime[i]==1)
        {
            if(i%10!=0)
            count[i]++;
        }
    count[i] += count[i-1];
    }
while (t--) {
int n;
cin >> n;
cout << count[n] << '\n';
}
8

thanks bro.
I am not getting TLE but getting wrong answer.

9

For each prime you need to check all if all it’s suffixes are also prime and none of the digits should be 0.
Here is my AC code

10

Thanks alot my friend for helping me out.

1 Like