Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.math.BigInteger;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Scanner;
- public class Primorial {
- static BigInteger zero = BigInteger.ZERO;
- static BigInteger one = BigInteger.ONE;
- static BigInteger two = BigInteger.valueOf(2);
- static BigInteger five = BigInteger.valueOf(5);
- public static void main(String[] args) {
- Scanner s = new Scanner(System.in);
- while (true) {
- primorial(s.nextBigInteger());
- }
- }
- static void primorial(BigInteger c) {
- BigInteger d = sqrt(c);
- BigInteger e = c.subtract(d.multiply(d));
- BigInteger f = two.multiply(d).add(one).subtract(e);
- Object[] Q = getPrimeSeries(d);
- BigInteger[] qPrimes = (BigInteger[]) Q[0];
- BigInteger q = (BigInteger) Q[1];
- BigInteger qc = q.multiply(c);
- BigInteger d_qc = sqrt(qc);
- BigInteger e_qc = qc.subtract(d_qc.multiply(d_qc));
- BigInteger f_qc = two.multiply(d_qc).add(one).subtract(e_qc);
- System.out.println("primes = " + Arrays.toString(qPrimes));
- System.out.println("q = " + q);
- System.out.println("qc = " + qc);
- System.out.println("d_qc = " + d_qc);
- System.out.println("e_qc = " + e_qc);
- System.out.println("f_qc = " + f_qc);
- /** Difference */
- //BigInteger difference = qc.subtract(c);
- //System.out.println("(qc - c) = " + difference);
- /** Trimming the difference */
- //BigInteger trimmed = difference;
- //BigInteger amountTrimmed = one;
- //while (isFactor(trimmed, two)) {
- // trimmed = trimmed.divide(two);
- //}
- //amountTrimmed = difference.divide(trimmed);
- //System.out.println("(qc - c) / " + amountTrimmed + " = " + trimmed);
- int mode = -3;
- System.out.println("mode = " + mode);
- /*
- 0 = iterate the odd column from c with all multiples of q primes
- 1 = iterate the even column from c with all multiples of q primes
- -1 = iterate the even column from c with only even multiples of q primes
- 2 = iterate the odd column from qc with all multiples of q primes
- 3 = iterate the even column from qc with all multiples of q primes
- -3 = iterate the even column from qc with only even multiples of q primes
- */
- //defaulting to mode 0
- BigInteger column = getOddColumn(e, f.negate());
- switch (mode) {
- default:
- case 0: column = getOddColumn(e, f.negate()); break;
- case -1:
- case 1: column = getEvenColumn(e, f.negate()); break;
- case 2: column = getOddColumn(e_qc, f_qc.negate()); break;
- case -3:
- case 3: column = getEvenColumn(e_qc, f_qc.negate()); break;
- }
- VQCElement test;
- BigInteger a;
- BigInteger b;
- //iterating variables
- BigInteger i;
- int j;
- BigInteger qPrime;
- BigInteger multiplier;
- boolean modelt0 = mode < 0;
- boolean ieq1 = true;
- long iterations = 0;
- solved:
- for (i = one;;) {
- for (j = 0; j < qPrimes.length; j++){
- iterations++;
- qPrime = qPrimes[j];
- multiplier = i;
- test = getElement(column, one, getT(column, multiplier.multiply(qPrime)));
- BigInteger gcd = c.gcd(test.a);
- if (!gcd.equals(one)) {
- a = gcd;
- b = c.divide(gcd);
- break solved;
- }
- }
- if (modelt0) {
- if (ieq1) {
- ieq1 = false;
- i = two;
- } else {
- i = i.add(two);
- }
- } else {
- i = i.add(one);
- }
- }
- System.out.println();
- System.out.println("iterations = " + iterations);
- System.out.println(test);
- System.out.println("x = " + qPrime + " * " + multiplier);
- System.out.println("c = " + a + " * " + b);
- System.out.println();
- }
- /** Returns Object[]{BigInteger[] qPrimes, BigInteger q} */
- static Object[] getPrimeSeries(BigInteger d) {
- BigInteger q = five;
- BigInteger nextPrime = five;
- ArrayList<BigInteger> primeList = new ArrayList<>();
- primeList.add(q);
- while (lt(q, d)) {
- nextPrime = nextPrime.nextProbablePrime();
- /** End in 01 constraint */
- if (nextPrime.toString(2).endsWith("01")) {
- q = q.multiply(nextPrime);
- primeList.add(nextPrime);
- }
- }
- BigInteger[] qPrimes = primeList.toArray(new BigInteger[0]);
- return new Object[]{qPrimes, q};
- }
- static VQCElement getElement(BigInteger e, BigInteger n, BigInteger t) {
- VQCElement v = new VQCElement();
- v.e = e;
- v.n = n;
- v.t = t;
- v.x = getX(e, t);
- /* define a(x) = ((x^2 + e) / (2*n)) // 1 */
- v.a = (v.x.pow(2)).add(e).divide(two.multiply(v.n));
- /* define define d(x) = ((x^2 + e) / (2*n) + x) // 1 */
- v.d = v.a.add(v.x);
- v.f = two.multiply(v.d).add(one).subtract(v.e);
- v.b = v.a.add(two.multiply(v.x)).add(two.multiply(v.n));
- v.c = v.a.multiply(v.b);
- return v;
- }
- static BigInteger getOddColumn(BigInteger e, BigInteger negative_f) {
- if (e.and(one).equals(zero)) return negative_f;
- else return e;
- }
- static BigInteger getEvenColumn(BigInteger e, BigInteger negative_f) {
- if (e.and(one).equals(zero)) return e;
- else return negative_f;
- }
- static BigInteger getX(BigInteger e, BigInteger t) {
- BigInteger subtrahend = one;
- if (e.and(one).equals(zero)) {
- subtrahend = two;
- }
- return two.multiply(t).subtract(subtrahend);
- }
- static BigInteger getT(BigInteger e, BigInteger x) {
- BigInteger addend = one;
- if (e.and(one).equals(zero)) {
- addend = two;
- }
- return x.add(addend).divide(two);
- }
- static boolean gt(BigInteger i, BigInteger i2) { return i.compareTo(i2) > 0; }
- static boolean gteq(BigInteger i, BigInteger i2) { return i.compareTo(i2) >= 0; }
- static boolean lt(BigInteger i, BigInteger i2) { return i.compareTo(i2) < 0; }
- static BigInteger sqrt(BigInteger n) {
- if (n.equals(zero)) return zero;
- if (gt(n, zero)) {
- int bitLength = n.bitLength(); //ceil(log(n, 2))
- BigInteger root = one.shiftLeft(bitLength >> 1); //right-shifting by one equals dividing by two
- while (!isSqrt(n, root)) {
- root = root.add(n.divide(root));
- root = root.shiftRight(1);
- }
- return root;
- }
- throw new ArithmeticException("Complex result");
- }
- static boolean isSqrt(BigInteger n, BigInteger root) {
- BigInteger lowerBound = root.multiply(root);
- BigInteger upperBound = root.add(one).multiply(root.add(one));
- return gteq(n, lowerBound) && lt(n, upperBound);
- }
- static class VQCElement {
- BigInteger a;
- BigInteger b;
- BigInteger c;
- BigInteger d;
- BigInteger td; //2d
- BigInteger e;
- BigInteger f;
- BigInteger i;
- BigInteger j;
- BigInteger n;
- BigInteger x;
- BigInteger t;
- int cm4;
- int em4;
- boolean isTrivial = false;
- public VQCElement clone() {
- VQCElement c = new VQCElement();
- c.a = a;
- c.b = b;
- c.c = this.c;
- c.d = d;
- c.td = td;
- c.e = e;
- c.f = f;
- c.i = i;
- c.j = j;
- c.n = n;
- c.x = x;
- c.t = t;
- c.cm4 = cm4;
- c.em4 = em4;
- c.isTrivial = isTrivial;
- return c;
- }
- String getCoordinates() {
- return "(" + e + ", " + n + ", " + t + ")";
- }
- String toElementString() {
- return "{" + e + ":" + n + ":" + d + ":" + x + ":" + a + ":" + b + "} ";
- }
- public String toString() {
- return toElementString() + getCoordinates();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment