package elte.java2_utikalauz5.math;

import java.math.*;
import java.util.Random;

/**
Prímszámkeresés.

@link.forrásfájl {@docRoot}/../data/math/src IsProbablePrim.java
@link.letöltés {@docRoot}/../data/math IsProbablePrim.jar
@since Java 2 Útikalauz programozóknak
*/
class IsProbablePrim {

    private final static BigInteger TWO = new BigInteger("2");

    /**
     * Egy páratlan, 3-nál nagyobb egész számról a tesztés eldönti, hogy
     * prím-e.
     *
     * @param n BigInteger bemenő páratlan, 3-nál nagyobb egész szám
     * @param t int biztonsági paraméter
     * @return boolean válasz
     */
    public boolean primTeszt(BigInteger n, int t) {
        if (n.compareTo(BigInteger.valueOf(3))<=0) return true;
        //n-t felírjuk n = 1 + 2**s * r alakban
        BigInteger thisMinusOne = n.subtract(BigInteger.ONE);
        BigInteger r = thisMinusOne;
        int s = r.getLowestSetBit();
        r = r.shiftRight(s);
        //Miller-Rabin teszt
        Random rnd = new Random();
        loop: for (int i=1; i<=t; i++) {
            //(1, n-1) intervallumban egy véletlenszám készítése
            BigInteger a;
            do {
                a = new BigInteger(n.bitLength(), rnd);
            } while (a.compareTo(BigInteger.ONE) <= 0 || a.compareTo(thisMinusOne) >= 0);

            BigInteger y = a.modPow(r, n);
            if (!y.equals(BigInteger.ONE) && !y.equals(thisMinusOne)) {
                int j = 1;
                while ( j<s && !y.equals(thisMinusOne)) {
                    y = y.modPow(TWO, n);
                    if (y.equals(BigInteger.ONE)) return false;
                    j++;
                }
                if (!y.equals(thisMinusOne)) return false;
            }
        }
        return true;
    }

 public static void main(String[] args) {
        IsProbablePrim mr = new IsProbablePrim();
  int start = Integer.parseInt(args[0]);
	int len = start + Integer.parseInt(args[1]);
	for (int i=start; i < len; i++) {
	 if (BigInteger.valueOf(i).isProbablePrime(20)) {
	  System.out.print(i + " ");
	 }
         if (mr.primTeszt(BigInteger.valueOf(i), 20)) {
             System.out.print("MR-Prím: " + i+" ");
         }
  }
  System.out.println();
 }
}