11064  Number Theory
Moderator: Board moderators
11064  Number Theory
I didnt get the clear idea of the problem? Can anybuddy help me !!
Thanks in Advance
Thanks in Advance
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.
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.
Last edited by mf on Sat Aug 12, 2006 8:23 pm, edited 1 time in total.
Here are some
My output:
Code: Select all
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
25
125
53387
2147483647
2147483646
2147483645
2147395600
982007569
765934
377744
216263
391530
669701
475509
349753
887257
417257
158120
699712
268352
772844
78706
Code: Select all
0
0
0
0
0
1
0
1
1
3
0
3
0
5
4
3
22
464
0
1612883455
519917158
1413369866
31335
417439
188871
0
290699
0
168782
0
126754
10214
96841
387863
153509
406785
42963
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Some cases:sakhassan wrote:Thanks... I got the point now.. .. can any one give me some more test cases.......
Code: Select all
1
2
3
4
5
6
7
8
9
10
11
12
13
2036223251
1831084566
2060163999
734985436
922144514
57163345
3542469
1661043921
291037751
589276374
2147483641
2147483642
2147483643
2147483644
2147483645
2147483646
2147483647
Code: Select all
0
0
0
0
0
1
0
1
1
3
0
3
0
65684648
1234917567
703269316
394243541
461785527
11983962
1565766
554109674
0
403189119
798354
1120426263
715827880
1079830757
519917158
1612883455
0

 New poster
 Posts: 6
 Joined: Fri Dec 30, 2005 10:29 am
Euler Totient Function?
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
Thank you

 New poster
 Posts: 6
 Joined: Fri Dec 30, 2005 10:29 am
This is how I am calculating the prime numbers..
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
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)y1.0)/(double)y;
while(x%y==0) x=x/y;
}
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 youmindboggler wrote:This is how I am calculating the prime numbers..
For Example, a number say 84...the sequence it run thru is...2(2 Times)...then 3 and finally 7.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)y1.0)/(double)y; while(x%y==0) x=x/y; }
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
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*(y1)/y , you can turn it to
totient/y*(y1) .
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*=(n1) ;
}
studying @ ntu csie

 Learning poster
 Posts: 60
 Joined: Sun Apr 16, 2006 7:59 pm
11064 i got abt 17 WA.........
hi there!
i'm again asking for ur help......
i test Martin's i/o and it's okay...
my code's below
pls give me such i/o for which my code is wrong.....
or tell me why its wrong!!!!
Thanks.......
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
or tell me why its wrong!!!!
Thanks.......
Last edited by ayeshapakhi on Tue Aug 15, 2006 8:23 am, edited 1 time in total.
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: 11064 i got abt 17 WA.........
Not working for this one: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
Code: Select all
2072798759
Code: Select all
91052
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 (p11) * p1^(k11) * (p21) * p2^(k21) * ... * (pm1) * pm^(km1).
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.
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 (p11) * p1^(k11) * (p21) * p2^(k21) * ... * (pm1) * pm^(km1).
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: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.
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.
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 pseudocode:
If at the end of this n is still greater than 1, it'll also be another prime factor.
In pseudocode:
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.
Last edited by mf on Mon Aug 14, 2006 7:19 am, edited 2 times in total.