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. OK, I Understand
 
Top