11073 - Euler's Totient Function

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid »

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?
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...
From 0 to 0

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 »

otherwise every thing alright? i mean my process ok?
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 »

still TLE
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by 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.
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by 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])
Self judging is the best judging!

Post Reply

Return to “Volume 110 (11000-11099)”