Java: Is there a more efficient way to do this? Checking for prime number

Question

Is there a better way to code this? This is the simplest way i could think of but many people have used more complicated code to determine if a number is a prime number.

public static void main(String[] args) {
    Scanner inputFromUser = new Scanner(System.in);
        int number;
        System.out.println("Please enter a number: ");
        number = inputFromUser.nextInt();
        if(number == 2 || number ==3){
            System.out.println("This number is prime");
        }
        else if(number%2 ==0 )
        {
            System.out.println("The number is not prime!");
        }
        else if(number%3 == 0){
            System.out.println("The number is not prime!");
        }
        else{
            System.out.println("This number is prime");
        }
    }
}

Yes, people generally use a Sieve for the GCD algorithm. And BigInteger already has a method for it. — Maarten Bodewes, Apr 20 '20 at 00:55
Well 25 is **not** prime. You need more code to determine if a number is prime. Something like [this](https://stackoverflow.com/a/46016050/2970947). — Elliott Frisch, Apr 20 '20 at 00:56
@ElliottFrisch I think that 25 is not a prime but is detected as such is the point that ScaryWombat was trying to make. MGG on the other hand probably meant trying all integers sequentially, so.... — Maarten Bodewes, Apr 20 '20 at 00:58
I'll take your word for it :) By the way, here are [the methods used for `BigInteger.probablePrime()`](https://stackoverflow.com/q/8744085/589259). — Maarten Bodewes, Apr 20 '20 at 01:02
@MaartenBodewes I had not seen SW's comment when I posted mine. We **both** failed to make the same point! It's like when you want salt but ask for pepper. Also 25 was the first non-prime that fails OP's tests. Multiples of 3 are tested. Multiples of 2 are tested. Multiples of 5 are not tested. And 25 is five squared. Could have said 49. 49 is not prime. There. — Elliott Frisch, Apr 20 '20 at 01:04
right, sorry guys i'm stupid, would it work if i implement (number% 5== 0) and (number%7==0) into the code. — MGG, Apr 20 '20 at 01:06
@MCG No. Because there are [more primes numbers](http://mathforum.org/dr.math/faq/faq.prime.num.html). And (while finite) a list of all primes in the range of integer would be quite long. — Elliott Frisch, Apr 20 '20 at 01:07
If you want a fairly simple algorithm (though maybe not super efficient), try checking to see if the number is divisible by any numbers below its square root and other than 1. I wouldn't try dividing by a static set of numbers unless you have a very specific data set. — Isaac Krementsov, Apr 20 '20 at 02:45

score 2 · Answer 1 · answered Apr 20 '20 at 01:09

2

The easiest way of doing this is using:

int number = 25;
System.out.println(BigInteger.valueOf(number).isProbablePrime(Integer.MAX_VALUE));

Which should print out false. If you want to have a pretty efficient method of finding primes, the methods are indicated in this answer (don't forget to vote up).

Testing all lower prime numbers yourself is possible, but beware that it is in the end not all that efficient. Typing them all in the code certainly isn't efficient; we try and let the computer do the work for us (create list of primes, test next values, if prime add them to list).

answered Apr 20 '20 at 01:09

Maarten Bodewes

90,524
13
150
263

thanks! sorry about that i just recently got into coding. – MGG Apr 20 '20 at 01:18
No problem and no need to be sorry. Remember, if you're doing the counting, you're probably doing something wrong :) Endless if statements are generally a clear indication that the code is not programmed efficiently. – Maarten Bodewes Apr 20 '20 at 01:20

WJS · Answer 2 · 2020-04-20T03:51:07.360

Using the Sieve of Erastosthenes is pretty efficient. It works as follows.

create a list of numbers form 2 to N
Find the first unmarked number starting with 2 (this just started so nothing is marked).
The first prime is 2
Starting with 2, mark off every following 2nd value in a list of numbers from 2 to N
The first unmarked slot after 2 is the next prime (3 in this case).
Now starting with 3, mark off every following 3rd value.

Keep repeating the above until an established limit is reached. Every value that has not been marked is a prime.

I used a BitSet to implement this. Here is the algorithm with comments.


 public List<Integer> sieve(int upperLimit) {
      BitSet hits = new BitSet();

      // return values
      List<Integer> primes = new ArrayList<>();

      for (int i = 2; i <upperLimit; i = hits.nextClearBit(i+1)) {
            // first unmarked bit starting with i
            // is a prime so record it.
            primes.add(i);

            // now starting with the next unmarked location,
            // begin marking with i+i
            for (int j = i+i; j < upperLimit; j += i) {
               hits.set(j);
            }
      }
      // once the limit has been reached, return the list
      // of primes.
      return primes;
   }

List<Integer> primes = sieve(40);
primes.forEach(System.out::print);

Prints

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Java: Is there a more efficient way to do this? Checking for prime number

2 Answers2