Skip to content
{{ message }}

Instantly share code, notes, and snippets.

shai-almog/PrimeMainMR.java

Created Oct 19, 2021
Prime number calculator used as part of a debugging tutorial on talktotheduck.dev
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import java.math.BigInteger; public class PrimeMainMR { public static int cnt = 0; // this is the RabinMiller test, deterministically correct for n < 341,550,071,728,321 // http://rosettacode.org/wiki/Miller-Rabin_primality_test#Python:_Proved_correct_up_to_large_N public static boolean isPrime(BigInteger n, int precision) { if (n.compareTo(new BigInteger("341550071728321")) >= 0) { return n.isProbablePrime(precision); } int intN = n.intValue(); if (intN == 1 || intN == 4 || intN == 6 || intN == 8) return false; if (intN == 2 || intN == 3 || intN == 5 || intN == 7) return true; int[] primesToTest = getPrimesToTest(n); if (n.equals(new BigInteger("3215031751"))) { return false; } BigInteger d = n.subtract(BigInteger.ONE); BigInteger s = BigInteger.ZERO; while (d.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) { d = d.shiftRight(1); s = s.add(BigInteger.ONE); } for (int a : primesToTest) { if (try_composite(a, d, n, s)) { return false; } } return true; } public static boolean isPrime(BigInteger n) { return isPrime(n, 100); } public static boolean isPrime(int n) { return isPrime(BigInteger.valueOf(n), 100); } public static boolean isPrime(long n) { return isPrime(BigInteger.valueOf(n), 100); } private static boolean try_composite(int a, BigInteger d, BigInteger n, BigInteger s) { BigInteger aB = BigInteger.valueOf(a); if (aB.modPow(d, n).equals(BigInteger.ONE)) { return false; } for (int i = 0; BigInteger.valueOf(i).compareTo(s) < 0; i++) { // if pow(a, 2**i * d, n) == n-1 if (aB.modPow(BigInteger.valueOf(2).pow(i).multiply(d), n).equals(n.subtract(BigInteger.ONE))) { return false; } } return true; } private static int[] getPrimesToTest(BigInteger n) { if (n.compareTo(new BigInteger("3474749660383")) >= 0) { return new int[]{2, 3, 5, 7, 11, 13, 17}; } if (n.compareTo(new BigInteger("2152302898747")) >= 0) { return new int[]{2, 3, 5, 7, 11, 13}; } if (n.compareTo(new BigInteger("118670087467")) >= 0) { return new int[]{2, 3, 5, 7, 11}; } if (n.compareTo(new BigInteger("25326001")) >= 0) { return new int[]{2, 3, 5, 7}; } if (n.compareTo(new BigInteger("1373653")) >= 0) { return new int[]{2, 3, 5}; } return new int[]{2, 3}; } public static void main(String[] args) throws InterruptedException { for (int i = 2; i < Math.pow(10, 9); ++i) { if (isPrime(i)) { cnt++; } Thread.sleep(1); } System.out.println("Total number of primes: " + cnt); } }
to join this conversation on GitHub. Already have an account? Sign in to comment