11073 - Euler's Totient Function

[Towhid]

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?

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]

otherwise every thing alright? i mean my process ok?

[shanto86]

still TLE

[mf]

Your program is too slow for some inputs, for example 958003200.

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?

I don't think it matters much how you check primality,
My program uses trial division by all odd integers up sqrt(n) and still runs in time.

[shanto86]

well... i want to be sure about my method:

1. fist generate all the primes upto: sqrt(1e9).
2. By BKTRK see if u can select prime if so then first take once, then twice... until it is impossible to take more and each time call BKTRK with next prime.

That's all.

[shanto86]

at last AC

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

Code: Select all

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