Hi,

I have tried a lot during the contest to submit CHEFHACK problem:

http://www.codechef.com/JAN13/problems/CHEFHACK

but it always give me time limit exceeding …kindly help me ??

this is my solution:

http://www.codechef.com/viewsolution/1715546

Hi,

I have tried a lot during the contest to submit CHEFHACK problem:

http://www.codechef.com/JAN13/problems/CHEFHACK

but it always give me time limit exceeding …kindly help me ??

this is my solution:

http://www.codechef.com/viewsolution/1715546

You should use usual array instead of map.

So that you can find the index of each prime in **O(1)** time instead of **O(log P)** time,

where **P** is the total number of primes less than **10 ^{7}**.

Namely, just declare variable mymap as `int mymap[MAX]`

.

But wait. I’ve just noticed the following loop in your code

int ans=1; for (int r = 2; r < a*[j]; r++) { if(a*[j]%r==0) { ans=0; break; } }

This slow down your program drastically.

You should use array `data[]`

to check whether number is prime in **O(1)** time.

Note that after the Sieve loop data* = i only for prime numbers i.

Hence instead of this loop you could simply write

int ans = 1; if(data[a*[j]] == 0) { ans = 0; }

but still i am getting wrong answer ?? please point out my mistake …??

http://www.codechef.com/viewsolution/1724277