Miller-prime-test.java

/* Miller-Rabin primality test, iteration signifies the accuracy of the test */
// test number if p is prime or not using 'iterations'.
booleanMiller(longp,intiteration){
longLOWER_RANGE = 1; //assign lower range value
longUPPER_RANGE = p-1; //assign upper range value
RandomrandomGenerator = newRandom();
if(p<2){
returnfalse;
 }
if(p!=2 && p%2==0){
returnfalse;
 }
longs=p-1;
while(s%2==0){
s/=2;
 }
for(inti=0;i<iteration;i++){
longrandomValue = LOWER_RANGE + (long)(randomGenerator.nextDouble()*(UPPER_RANGE - LOWER_RANGE));
longa = randomValue %(p-1)+1,temp=s;
longmod= pow(a,temp,p);
while(temp!=p-1 && mod!=1 && mod!=p-1){
mod = pow(mod,mod,p);
temp *= 2;
 }
if(mod!=p-1 && temp%2==0){
returnfalse;
 }
 }
returntrue;
 }
// sieve

// Better Optioin : BigInteger is Probable prime
importjava.io.*;
importjava.util.*;
importjava.text.*;
importjava.math.*;
importjava.util.regex.*;

publicclassSolution {

staticlongnext(longx) {
if (x == 0) {
return0;
 }
longy = x / 10;
longy1 = next(y + (x % 10 > 7 ? 1 : 0));
if (y != y1) {
return10 * y1 + 2;
 }
returny1 * 10 + (x % 10 <= 2 ? 2 : x % 10 <= 3 ? 3 : x % 10 <= 5 ? 5 : 7);
 }

publicstaticvoidmain(String[] args) {
Scannerin = newScanner(System.in);
longfirst = in.nextLong();
longlast = in.nextLong();
longans = 0;
first = next(first);
while (first <= last) {
//System.err.println(first);
if (BigInteger.valueOf(first).isProbablePrime(20)) { // 20 is rounds
ans++;
 }
first = next(first + 1);
 }
System.out.println(ans);
 }
}