It's really pity you get constantly TLE. The time limit has been changed because during the contest there is a large load on judge host and the solutions run up to two times slower.

Let's try to improve your code.

Firstly let's start from the sieve of Eratosthene:

- Code: Select all
`void seive()`

{

for(int i=3; i<=13333292; i+=2)

{

if(mp[i]==0)

{

prime[len++]=i;

for(int j=i*2; j<=13333292; j+=i)

{

mp[j]=1;

}

}

}

}

It's not optimized:

- I do not know why you have commented //bitset<13333295>mp; Does it not work properly? In order to set one bit you are accessing four bytes in your code, increasing the execution time. At the last end you can define mp as char.
- You start internal cicle from 2*i. Why? So your sieve has O(N*log(N)) time complexity. You can easily start it from i*i (with overflow checking), reducing the complexity to O(N*log(log(N))). For large N it is significantly better. Moreover you can use more advanced algorithms like this, but it is not necessary to solve this problem.
- You can increase j on 2*i, not simply i.

Your code is full of constans, but you can derive some of them from other constants. For example:

- Code: Select all
`const int maxv = 200000000;`

const int limit = maxv / 15;

Is the value 13333295 correct?

Here is my C-incarnation of the sieve:

- Code: Select all
`#define MAXV 200000000`

#define LIMIT (MAXV / 15)

#define PHAS(_n) (pbits[(_n)>>5] & (1u << ((_n) & 0x1f)))

#define PSET(_n) (pbits[(_n)>>5] |= (1u << ((_n) & 0x1f)))

unsigned int pbits[LIMIT/32+1];

int pr[1000000];

int pc;

void gen( void )

{

int i, j, mx = (int) sqrt( LIMIT );

pc = 0;

for( i = 3; i < LIMIT; i += 2)

if( !PHAS(i) )

{

pr[pc++] = i;

if( i <= mx )

for( j = i*i; j <= LIMIT; j += 2*i) PSET(j);

}

}

It uses the array

pbits as a bitset.