How to check if a 100 digit integer is prime or not in Java?

Question

I am having an integer number which consists of 100 digits and I want to check whether the number is prime or not. How am I supposed to check?

I have tried using long integer but as you know it is impossible. So, is there any other way to solve it. If yes, then please provide me sample code for it.

I expect to get output as only prime and not prime when I enter any 100 digit integer.

Thanks @Some Name for your help. – Alexa Jan 20 '19 at 19:51 — Alexa, Jan 20 '19 at 19:51

SWETA KESUR · Accepted Answer · 2019-01-20T19:45:09.267

1

As you already know that we cannot do this task by using long integer. Compulsory you will have to use the concept of BigInteger class. It has one method named as isProbablePrime to determine whether the number is prime or not.

You can try this code:

public class MyCode {
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String n = scanner.nextLine();
        scanner.close();

        BigInteger b = new BigInteger(n);
        Boolean b1,b2,b3;
        b1 = b.isProbablePrime(-1);
        b2 = b.isProbablePrime(0);
        b3 = b.isProbablePrime(1);

        if(b1 == true && b2 == true && b3 == true){
            System.out.println("prime");
        }
        else{
            System.out.println("not prime");
        }
    }
}

To get more information about BigInteger class visit: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#isProbablePrime%28int%29

edited Jan 20 '19 at 19:45

answered Jan 20 '19 at 19:39

SWETA KESUR

321
2
10

1

Thanks @SWETA KESUR. It works perfectly and by using this class and method you simplified a complex task of mine. It is very helpful – Alexa Jan 20 '19 at 19:50
2

don't forget there must be a reason for naming the method `isProbablePrime` instead of just `isPrime`... – user85421 Jan 20 '19 at 19:50
2

can you explain that certainty of (-1,0,1) – Ryuzaki L Jan 20 '19 at 20:02
1

According to the definition of `isProbablePrime` method it will return `true` if this BigInteger is probably prime, `false` if it's definitely composite. [`If certainty is ≤ 0, true is returned`](https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#isProbablePrime%28int%29). So, for certainty 0 and 1 we will get the result as true but main check is for certainty as 1 if we receive as `true` then it is prime number else it is composite. – SWETA KESUR Jan 20 '19 at 20:33
@Deadpool: you're reading the docs for the next method on the page, `compareTo()`, not `isProbablePrime()`. – President James K. Polk Jan 21 '19 at 15:38
2

@SWETAKESUR: no, that is not how the `certainty` parameter works for `certainty > 0`, as the docs explain. – President James K. Polk Jan 21 '19 at 15:41
1

I agree with @JamesKPolk here, you are misreading [the documentation](https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#isProbablePrime-int-). If you look at some [source code](http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/00cd9dc3c2b5/src/share/classes/java/math/BigInteger.java#l2451) you clearly can see it's just ignoring you if given a negative or zero input. Those calls do _nothing_. You then ask for a single M-R test to be performed. Fortunately at this size it is quite accurate for non-adversarial inputs. – DanaJ Jan 21 '19 at 20:40
@DanaJ: although, by my reading of the source code, the docs are also incorrect. For bigints > 256 bits the certainty parameter appears to be completely ignored. – President James K. Polk Jan 21 '19 at 21:19
@JamesKPolk Technically incorrect regarding the certainty guarantee, though IMO it's a better overall solution. Over 100 bits they add a non-strong Lucas test (they mis-name it Lucas-Lehmer, which is a different test, but that doesn't affect the execution). This is excellent and recommended, though they ought to use the strong or extra strong version. The certainty parameter is used though capped in all cases. – DanaJ Jan 22 '19 at 16:47
@DanaJ: `if (sizeInBits < 256) { rounds = 27; }` This does not use the certainty parameter. – President James K. Polk Jan 22 '19 at 21:42
@JamesKPolk Right after that comes: `rounds = n < rounds ? n : rounds;`. n is ceil(certainty/2). So all the `rounds = ?` lines are setting a cap. In the case of certainty=1 being passed in, only one round is performed regardless of the input size. – DanaJ Jan 23 '19 at 22:16
I agree with the comments here, this answer seems completely wrong. Per the docs (and the first line of the implementation), `b1` and `b2` will ALWAYS return true, so this only tells us if that number is prime with a certainty of 1-1/2^1 = 0.5, which means 50% probability that this number is prime. – Ricola May 09 '21 at 14:01

How to check if a 100 digit integer is prime or not in Java?

1 Answers1