10299  Relatives
Moderator: Board moderators

 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 WeiMing Chen on Sat Feb 04, 2006 8:53 am, edited 3 times in total.

 Experienced poster
 Posts: 122
 Joined: Sun Nov 13, 2005 10:25 am
 Location: Taiwan
You have to take care of more number of primes. For example, output of
are
Use code tagging for posting codes.
Code: Select all
997485889
998623201
999002449
Code: Select all
997454306
998591600
998970842

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

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

 New poster
 Posts: 30
 Joined: Wed Oct 23, 2002 6:53 am

 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.
Thanx in advance.
Code :
Removed after accpeted .
Then too I am getting TLE.
Smbd help me.
Thanx in advance.
Code :
Removed after accpeted .
Last edited by Ankur Jaiswal on Tue May 02, 2006 11:30 am, edited 1 time in total.

 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.
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.
Clever bruteforce 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.

 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) *(num1);
so i dont think that this condition is wrong.
If it is not 1 then it will obviously be a prime number... therefore i have done ans=(ans/num) *(num1);
so i dont think that this condition is wrong.

 New poster
 Posts: 31
 Joined: Sat Apr 01, 2006 6:24 am
 Contact:
Solution
thanks a lot.
But now i am getting WA.
But now i am getting WA.