11064 - Number Theory

sakhassan · Post by **sakhassan** » Sat Aug 12, 2006 6:23 pm

I didnt get the clear idea of the problem? Can anybuddy help me !!

Thanks in Advance

mf · Post by mf » Sat Aug 12, 2006 6:29 pm

Did you fail to understand the problem, or can't solve it?

If it's the former, the whole problem is: find out, how many integers m are there, satisfying: 1<=m<=n, and gcd(m,n)!=1, and gcd(m,n)!=m.
That is, how many integers between 1 and n are there, which are not relatively prime with n, and yet are not n's divisors.

sakhassan · Post by **sakhassan** » Sat Aug 12, 2006 8:03 pm

Thanks... I got the point now..

.. can any one give me some more test cases.......

mf · Post by mf » Sat Aug 12, 2006 8:08 pm

Here are some

Code: Select all

My output:

Code: Select all

Martin Macko · Post by **Martin Macko** » Sat Aug 12, 2006 8:10 pm

sakhassan wrote:Thanks... I got the point now.. .. can any one give me some more test cases.......

Some cases:

Code: Select all

My AC's outputs:

Code: Select all

mindboggler · Post by **mindboggler** » Sun Aug 13, 2006 12:45 pm

I am using Euler Totien'ts function....which is timing out for some cases because it is difficult to find the prime numbers. Please give me a small hint.

Thank you

sohel · Post by **sohel** » Sun Aug 13, 2006 2:36 pm

Euler Totien'ts function should not time out..
.. i used this and got AC.

What do you mean by 'it's difficult to find the prime numbers' ?

You have to use the prime numbers upto sqrt(N) only and there are only few of them.

mindboggler · Post by **mindboggler** » Sun Aug 13, 2006 4:36 pm

This is how I am calculating the prime numbers..

Code: Select all

//Here n is the number for which I am trying to find the primes
int x=n;
double totient = n;
int y=2;
while(x!=0) {
  while(x%y!=0 && y<x) y++;
  if (y>x || y==n) break;
  totient *= ((double)y-1.0)/(double)y;
  while(x%y==0) x=x/y;
}

For Example, a number say 84...the sequence it run thru is...2(2 Times)...then 3 and finally 7.

I tried random cases and have seen that for some, the code sticks a lot of time inside the loop.

Please point out where the mistake is

Thank you

SRX · Post by **SRX** » Sun Aug 13, 2006 6:07 pm

mindboggler wrote:This is how I am calculating the prime numbers..
Code: Select all
//Here n is the number for which I am trying to find the primestwhile(x!=0) {
  while(x%y!=0 && y<x) y++;
  if (y>x || y==n) break;
  totient *= ((double)y-1.0)/(double)y;
  while(x%y==0) x=x/y;
}
For Example, a number say 84...the sequence it run thru is...2(2 Times)...then 3 and finally 7.

I tried random cases and have seen that for some, the code sticks a lot of time inside the loop.

Please point out where the mistake is

Thank you

ok , some suggestions to you

1 you should try all prime numbers instead of all numbers
( I mean 2 3 5 7 , instead of 2 3 4 5 6 7 8 .... )
2 try prime numbers until ( prime*prime<=n ) , because when
prime*prime>n , now n is a prime

3 you don't need to use double , just int is enough , because
when you do totient*(y-1)/y , you can turn it to
totient/y*(y-1) .

Code: Select all

  example :
  int i=0 , totient = n ;    // prime counter 
  while ( i<size(prime) && prime[i]*prime[i]<=n ) {
     if ( n%prime[i]==0 ) {
       while ( n%prime[i]==0 )
       n/=prime[i] ; 
       totient/=prime[i] , totient*=(prime[i]-1) ;
     }
    i++ 
  }
  if ( n!=1 ) {
       //  now n is a prime , too 
      totient/=n , totient*=(n-1) ; 
  }

ayeshapakhi · Post by **ayeshapakhi** » Sun Aug 13, 2006 9:29 pm

hi there!
i'm again asking for ur help......
i test Martin's i/o and it's okay...
my code's below

Code: Select all

removed after AC

pls give me such i/o for which my code is wrong.....
or tell me why its wrong!!!!
Thanks.......

Martin Macko · Post by **Martin Macko** » Sun Aug 13, 2006 11:37 pm

ayeshapakhi wrote:hi there!
i'm again asking for ur help......
i test Martin's i/o and it's okay...
my code's below

Not working for this one:

Code: Select all

2072798759

My AC's output:

Code: Select all

leocm · Post by **leocm** » Mon Aug 14, 2006 5:50 am

I'm not understanding how to compute this problem.

Could anybody feel a general explanation of what should be done?

I know the Euler's totient function, but I don't have idea of how implements it in an efficient way.

Thank you.

Darko · Post by **Darko** » Mon Aug 14, 2006 6:39 am

Well, you can count divisors and calculate the totient function at the same time, because both can be calculated from the prime factorization.

If a number is given as n = p1^k1 * p2^k2 * ... * pm^km, number of its divisors is (k1+1) * (k2+1) * ... * (km+1) and totient function is (p1-1) * p1^(k1-1) * (p2-1) * p2^(k2-1) * ... * (pm-1) * pm^(km-1).

How to do prime factorization efficiently? Well, I don't know, I just go through primes in order, nothing fancy, and it usually works fine.

leocm · Post by **leocm** » Mon Aug 14, 2006 7:04 am

Darko wrote:How to do prime factorization efficiently? Well, I don't know, I just go through primes in order, nothing fancy, and it usually works fine.

Yes, I understand your point, but the question is:

Do you have a list of the primes to do this? Until which number? If not, how can you "go through primes in order"?

Thank you.

mf · Post by mf » Mon Aug 14, 2006 7:12 am

Try to divide n by all primes up to sqrt(n).
If at the end of this n is still greater than 1, it'll also be another prime factor.

In pseudo-code:

Code: Select all

p = 2
while p*p <= n do
  while p divides n do
    n=n/p
    output p as a prime factor
  p=p+1   // or you can replace p by next larger prime here, but this will work, too
if n > 1 then output n.

OJ Board

11064 - Number Theory

11064 - Number Theory

Euler Totient Function?

11064 i got abt 17 WA.........

Re: 11064 i got abt 17 WA.........