Algorithm/Mathematices.java at main · suzelkhan1177/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
public class Mathmatics{

    public static int TrailingZero(int n) {

    	  int result =0;

    	  for(int i=5; i<=n; i=i*5) {
    		   result = result + n/i;
    	  }

    	  return result;
    }


    public static boolean[]  SieveOfEratosthenes(int n) {


//        if (n<3){
//    	return 0;
//    }


     int count =0;

     boolean isPrime[] = new boolean[n];
 	    Arrays.fill(isPrime, true);

 	  isPrime[0] =false;
 	  isPrime[1] = false;

 	  for(int i=2; i <n; i++) {
 		  if(isPrime[i] == true){
               count++;
 		  for(int j = i+i; j <n; j += i) {

 			  isPrime[j] =false;
                  }
           }
 	  }


     return isPrime;
    }

//    Greatest Common Divisor (GCD).
    public static int GCDfun1(int a, int b) {

    	   if(b==0)
    		 return a;

    	   return GCDfun1(b, a%b);
    }


    public static int GCDfun2(int a, int b) {

 	  while(b != 0) {
 		  int rem = a%b;
 		    a=b;
 		    b=rem;
 	  }

 	   return a;
 }

 public static int ModuloArithmetic(int a, int b) {

	 int res = 1;

	 while(b >0) {

	 if((b&1) != 0) {
		 res = res *a;
	 }

	 a = a*a;
	 b = b>>1;

	 }

	 return res;

 }

 public static long ModuloArithmetic(long a, long b, int n) {

	 long res = 1;

	 while(b >0) {

	 if((b&1) != 0) {
		 res = ( res * a%n) %n;
	 }

	 a = (a%n * a%n )%n;
	 b = b>>1;

	 }

	 return res;

 }

	public static void main(String[] args) {


		int n =20;

		boolean[] isPrime = SieveOfEratosthenes(n);

		  for(int i=0; i<n; i++) {

			  if(isPrime[i] == true)
				  System.out.print( i+ " ");
	    }
		  System.out.println();
		System.out.println("Trailing Zero " +TrailingZero(12));

		System.out.println("GCD = " + GCDfun1(42,24));
		System.out.println("Fast Power = "+ ModuloArithmetic(3, 5));
		System.out.println("Fast Power Long = "+ ModuloArithmetic(345464, 5, 10000007));

	}

}