You can use 3*10^7 size char array for flagging, if use bitwise func, 8 times of that. So, you can flag primes upto this range and modify the PRIME function accordingly...shanto86 wrote: well... in my process i had written PRIME() function which returns 0/1 according to whether it is prime or not when i need to check primality for a number > sqrt(10^9) but no one here mentioned for such process. so am i doing inefficient some where?

## 11073 - Euler's Totient Function

**Moderator:** Board moderators

From 0 to 0

I don't think it matters much how you check primality,Well... in my process i had written PRIME() function which returns 0/1 according to whether it is prime or not when i need to check primality for a number > sqrt(10^9) but no one here mentioned for such process. so am i doing inefficient some where?

My program uses trial division by all odd integers up sqrt(n) and still runs in time.

at last AC

well... i added one more cutoff that is:

well... i added one more cutoff that is:

Code: Select all

` if(n < prime[pos]*(prime[pos]-1) && n+1>prime[pos])`

Self judging is the best judging!