• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Dec 8th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <stdio.h>
2. #include <stdlib.h> // because we need abs()
3.
4. // Divides a by m, and outputs positive remainder
5. //input: integer a,m
6. //output: positive remainder of a/b
7. int imod(int a, int m)
8. {
9.     a %= m;
10.     return (a<0)? a+abs(m) : a; // adds abs(m) if remainder is negative, does nothing if positive
11. }
12.
13. //Solves ax+by=1 for integer using Extended Euclidian Algorithm
14. //Input : integer a,b
15. //Output(via pointer) : Answer: x,y, GCD of a,b: d
16. void exEuclid(int a, int b, int *x, int *y, int *d)
17. {
18.     int s0,s1,s2,t0,t1,t2,sgn,r,q;
19.
20.     s0 = 1;
21.     s1 = 0;
22.     t0 = 0;
23.     t1 = 1;
24.
25.     sgn = 1;
26.
27.     while(b!=0) // Extended Euclidean Algorithm
28.     {
29.         r = imod(a,b);
30.         q = a/b;
31.         a = b;
32.         b = r;
33.         s2 = s1;
34.         s1 = q*s1+s0;
35.         s0 = s2;
36.         t2 = t1;
37.         t1 = q*t1+t0;
38.         t0 = t1;
39.         sgn = -sgn;
40.     }
41.     *d = a;
42.     *x = sgn*s0;
43.     *y = -sgn*t0;
44. }
45.
46. int main()
47. {
48.     int i,n,phi,dummy,gcd;
49.     phi = 1;
50.     printf("This program calculates phi(n) where phi is the euler totient function\n");
51.     printf("Input n\n");
52.     scanf("%d",&n);
53.     for (i=2;i<n;i++)
54.     {
55.         exEuclid(i,n,&dummy,&dummy,&gcd);
56.         if(gcd == 1){ phi += 1;}
57.     }
58.     printf("phi(%d) = %d\n",n,phi);
59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top