Add New Prime Check (#3036)

omarmahamid · web-flow · commit 1a230bd61e64 · 2022-04-29T16:30:05.000+03:00
diff --git a/src/main/java/com/thealgorithms/maths/PrimeCheck.java b/src/main/java/com/thealgorithms/maths/PrimeCheck.java
@@ -10,9 +10,15 @@ public static void main(String[] args) {
         System.out.print("Enter a number: ");
         int n = scanner.nextInt();
         if (isPrime(n)) {
-            System.out.println(n + " is a prime number");
+            System.out.println("algo1 verify that " + n + " is a prime number");
         } else {
-            System.out.println(n + " is not a prime number");
+            System.out.println("algo1 verify that " + n + " is not a prime number");
+        }
+
+        if (fermatPrimeChecking(n, 20)) {
+            System.out.println("algo2 verify that " + n + " is a prime number");
+        } else {
+            System.out.println("algo2 verify that " + n + " is not a prime number");
         }
         scanner.close();
     }
@@ -38,4 +44,41 @@ public static boolean isPrime(int n) {
         }
         return true;
     }
+
+    /**
+     * *
+     * Checks if a number is prime or not
+     *
+     * @param n the number
+     * @return {@code true} if {@code n} is prime
+     */
+    public static boolean fermatPrimeChecking(int n, int iteration){
+      long a;
+      int up = n - 2, down = 2;
+      for(int i=0;i<iteration;i++){
+        a = (long)Math.floor(Math.random()*(up - down + 1) + down);
+        if(modPow(a,n-1,n) != 1){
+          return false;
+        }
+      }
+      return true;
+    }
+
+
+    /**
+     * *
+     * @param a basis
+     * @param b exponent
+     * @param c modulo
+     * @return (a^b) mod c
+     */
+    private static long modPow(long a, long b, long c){
+        long res = 1;
+        for (int i = 0; i < b; i++)
+        {
+            res *= a;
+            res %= c;
+        }
+        return res % c;
+    }
 }
