How to modify a series of functions in Long for BigInteger?

-5

The code below checks whether a number is prime in a sequence generated from a formula:

package dec;

import java.util.ArrayList;
import java.util.List;

public class Dec {

private static boolean ehPrimo(long d) {

long n = d;
long raiz = (long) Math.sqrt(n);
for (long k = 2; k <= raiz; k++) {
    if (n % k == 0) return false;
 }
return true;
} 

public static void main(String[] args) {

List<Long> primeiraLista = new ArrayList();
List<Long> segundaLista = new ArrayList();
for (long a = 1; a <= 100; a++) {
long c = a + 69;
if (ehPrimo(c)) {
primeiraLista.add(c);
} else {
long d = c + 6;
if (ehPrimo(d)) {
    segundaLista.add(d);
  }
 }
}
System.out.printf("Primeira lista %s%n", primeiraLista);
System.out.printf("Segunda lista %s%n", segundaLista);       
 }
}

From 1 to 100 of the 2 lists only the Cousins:

The only problem is that this code is in Long, how to do it all in BigInteger for larger numbers?

    
asked by anonymous 21.06.2016 / 23:30

1 answer

3

Basically you need to split the problem into two parts.

1. Determining if a number is prime

This is the part that has been resolved by other issues. Based on your algorithm, a possible implementation would be:

boolean ehPrimo(long n) {
    long raiz = (long) Math.sqrt(n);
    for (long k = 2; k <= raiz; k++) {
        if (n % k == 0) return false;
    }
    return true;
}

2. Generating the numerical sequence according to the two formulas

When you define a formula or equation, you do not do it with several lines as you did. It could have been written in a much simpler way.

If b = a + 37 and c = a + b , we can replace b in the second equation and get c = a + a + 37 .

The same is used for the calculation of d , where we can simply write that d = c + 8 .

Now we have a is the variable and we can make a loop such that a varies from 1 to 100 . At each iteration, we can calculate the values of c and d as needed.

Finally, we can add the values of c primes in a list and the values of d primes in another list.

Code sample:

List<Long> primeiraLista = new ArrayList();
List<Long> segundaLista = new ArrayList();
for (long a = 1; a <= 100; a++) {
    long c = a + a + 37;
    if (ehPrimo(c)) {
        primeiraLista.add(c);
    } else {
        long d = c + 8;
        if (ehPrimo(d)) {
            segundaLista.add(d);
        }
    }
}

Finally, we can print the lists as needed. For example:

System.out.printf("Primeira lista %s%n", primeiraLista);
System.out.printf("Segunda lista %s%n", segundaLista);

Update

After updating the question to BigInteger the code could be changed as follows:

public class StrangePrimeFormulaWithBigInteger {

    public static void main(String[] args) {
        List<BigInteger> primeiraLista = new ArrayList();
        List<BigInteger> segundaLista = new ArrayList();
        BigInteger limit = new BigInteger("100");
        BigInteger n37 = new BigInteger("37");
        BigInteger n8 = new BigInteger("8");
        for (BigInteger a = BigInteger.ONE; a.compareTo(limit) <= 0; a = a.add(BigInteger.ONE)) {
            BigInteger c = a.add(a).add(n37);
            if (ehPrimo(c)) {
                primeiraLista.add(c);
            } else {
                BigInteger d = c.add(n8);
                if (ehPrimo(d)) {
                    segundaLista.add(d);
                }
            }
        }

        System.out.printf("Primeira lista %s%n", primeiraLista);
        System.out.printf("Segunda lista %s%n", segundaLista);
    }

    public static boolean ehPrimo(BigInteger n) {
        BigInteger raiz = sqrt(n);
        for (BigInteger k = new BigInteger("2"); k.compareTo(raiz) <= 0; k = k.add(BigInteger.ONE)) {
            if (n.mod(k).equals(BigInteger.ZERO)) return false;
        }
        return true;
    }

    /**
     * Extraído de https://stackoverflow.com/a/16804098/1683070
     */
    public static BigInteger sqrt(BigInteger x) {
        BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);
        BigInteger div2 = div;
        // Loop until we hit the same value twice in a row, or wind
        // up alternating.
        for(;;) {
            BigInteger y = div.add(x.divide(div)).shiftRight(1);
            if (y.equals(div) || y.equals(div2))
                return y;
            div2 = div;
            div = y;
        }
    }

}

Some considerations:

  • Now the lists are with the new type: List<BigInteger> .
  • Numbers must be instantiated and not directly assigned: BigInteger n8 = new BigInteger("8"); .
  • Instantiated the numbers 37 , 8 and 100 before the loop to avoid instantiating them repeatedly at each iteration.
  • All mathematical operations need to use BigInteger methods such as add , divide , mod (rest).
  • Comparisons are made using equals and compareTo , not == .
  • a.compareTo(limit) <= 0 is the same as a <= limit
  • Java does not provide a method to calculate the root of this type of variable. For a reliable solution you can use a library like Apache Commons Math or Google Guava. In this case I have inserted an implementation available in an SOen response .
  • Calculations with variables BigInteger and BigDecimal can reach several orders of magnitude slower than with primitive types, although in that case whose computation is very slight this difference is almost imperceptible.
23.06.2016 / 06:37