Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h> // because we need abs()
- // Divides a by m, and outputs positive remainder
- //input: integer a,m
- //output: positive remainder of a/b
- int imod(int a, int m)
- {
- a %= m;
- return (a<0)? a+abs(m) : a; // adds abs(m) if remainder is negative, does nothing if positive
- }
- //Solves ax+by=1 for integer using Extended Euclidian Algorithm
- //Input : integer a,b
- //Output(via pointer) : Answer: x,y, GCD of a,b: d
- void exEuclid(int a, int b, int *x, int *y, int *d)
- {
- int s0,s1,s2,t0,t1,t2,sgn,r,q;
- s0 = 1;
- s1 = 0;
- t0 = 0;
- t1 = 1;
- sgn = 1;
- while(b!=0) // Extended Euclidean Algorithm
- {
- r = imod(a,b);
- q = a/b;
- a = b;
- b = r;
- s2 = s1;
- s1 = q*s1+s0;
- s0 = s2;
- t2 = t1;
- t1 = q*t1+t0;
- t0 = t1;
- sgn = -sgn;
- }
- *d = a;
- *x = sgn*s0;
- *y = -sgn*t0;
- }
- int main()
- {
- int i,n,phi,dummy,gcd;
- phi = 1;
- printf("This program calculates phi(n) where phi is the euler totient function\n");
- printf("Input n\n");
- scanf("%d",&n);
- for (i=2;i<n;i++)
- {
- exEuclid(i,n,&dummy,&dummy,&gcd);
- if(gcd == 1){ phi += 1;}
- }
- printf("phi(%d) = %d\n",n,phi);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement