## 10299 - Relatives

Moderator: Board moderators

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

### 10299 TLE... (now WA) -> TLE again

Got AC now, thanks everyone's help.
Last edited by Wei-Ming Chen on Sat Feb 04, 2006 8:53 am, edited 3 times in total.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Precalculate the prime numbers.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
I fixed my code, but it changed to WA now.....
Can you help again?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
You have to take care of more number of primes. For example, output of

Code: Select all

``````997485889
998623201
999002449``````
are

Code: Select all

``````997454306
998591600
998970842``````
Use code tagging for posting codes.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
I changed my code.
But why TLE again?
Should I make a int x[1000000000] ?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Wei-Ming Chen wrote:I changed my code.
But why TLE again?
Should I make a int x[1000000000] ?
nope..
sqrt(1000000000) will be enough..

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
Maybe I should think why I used sqrt(1000000000) and got TLE.......

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am
one of your code problem is that num must be longint,
because, the problem states that n<1000000000.

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

### 10299 TLE

I have used sieve to calculate the prime numbers. Then I used Euler's fonction to calculate the number of relatives.
Then too I am getting TLE.
Smbd help me.
Code :
Removed after accpeted .
Last edited by Ankur Jaiswal on Tue May 02, 2006 11:30 am, edited 1 time in total.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Dear - Ankur Jaiswal!

Euler Phi-function works fine here - I did got AC, but long after series of TLE too...
Last edited by serur on Sat Apr 14, 2012 3:26 pm, edited 1 time in total.

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

### Solution to 10299

I too have used Euler Phi function to solve this question.
But I first calculated prime numbers using Sieve so as to get the prime numbers in lesser time. But then too i am getting TLE. Plz give more hints to solve this problem.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Clever brute-force check (however weird it sounds ) is enough - get rid of factor 2 and run odds. Don't forget about square roots. And also that this algo not necesarily terminates with 1.
Last edited by serur on Sat Apr 14, 2012 3:32 pm, edited 1 time in total.

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

### Terminating condition on (num==1)

When num!=1 (but i>3401) in the function relatives() and the for loop is done with, then i am keeping a check onto num (whether it is 1 or not).
If it is not 1 then it will obviously be a prime number... therefore i have done ans=(ans/num) *(num-1);
so i dont think that this condition is wrong.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm