The main problem is: the algorithm contains a lot of divisions and a lot of function calls. A division can be very time consuming.
As Harish Ved said, the key is the sieve of Eratosthenes. It is one of the simplest and fastest way do determine if a number is prime. With that method, the problem can be solved by zero division and function call.
You should implement the sieve in the main function. You can find a lot of optimized examples on the internet. When You are done with that, You'll have an array, which contains the result of every
IsPrime() method you can call. From that point, you only have to check an element of the array to know of a number is prime.
Here You can find a sample sieve (this can be optimized, but probably this will be able to solve the problem in the given time limit too).
You need a maximum value (
MAXVAL), the primes smaller than that will be computed.
char *primes = (char*)malloc(MAXVAL*sizeof(char));
primes[i]=1; //allocating memory and filling with 1
} //setting the multiples of prime numbers to 0
This little algorithm will generate an array in wich the values at the primeth indexes will be 1, and other values will be 0. So after this, instead of calling Your
IsPrime function with a lot of divisions, the prime check of
n will look like
You can find a little working demonstration HERE