Number of prime numbers in a given range

Question

I've written a method that should return the numbers of prime numbers in a given range:

public static int numberOfPrim(int up){                 // Returns amount of primnumbers from 0 to up
    if(up<=0){
        return 0;
    }
    int primAmount = 0;
    for(int i = 1; i<=up ; i++){
        if(checkIfPrim(i) == true){
           primAmount++;
        }
    }
    return primAmount;
}

public static boolean checkIfPrim(int number){         // If number is prim -> return true
    if (number < 2){
        return false;
    }
    boolean prim = true;
    if(number == 2){
        return prim;
    }
    boolean[] con = new boolean[number];
    for(int i = 2; i < number; i++){
        if(number %i == 0) {
            con[i] = true;
        }
    }
    for(int j = 0; j < number; j++){
        if(con[j] == true){
            prim = false;
        }
    }
    return prim;
}

The code is working like I want it to. For example, numberOfPrim(10) should return 4 (2, 3, 5, 7). I'm just asking if there are any locations where I can improve my code, like shorten it or if there are any other possibilities to write such a method.

Answer 1

1. What is the purpose of shortening the term "Prime(s)" to Prim in your method names? IMO numberOfPrimes and checkIfPrime are more readable. The same is true for primAmount etc.
2. if(checkIfPrim(i) == true) can simply be if (checkIfPrim(i))
3. Your spacing is inconsistent. Generally, it is recommended to leave a space between a control structure (for, if, while etc.) and its following open paren, which you adhere to exactly once in checkIfPrim, but not elsewhere. The same applies to operators: Write up <= 0 instead of up<=0.

4. Your checkIfPrim method is grossly overcomplicated. First of all, you check every number up to number for divisibility, while it should be obvious that there can be no divisor greater than number / 2. Still, if you think about the problem, you will soon arrive at another conclusion, which is that you only need to check numbers up to sqrt(number), because you can write a * b = number (with a and b being positive integers), which is to say that a and b are divisors of number. Now, letting sqrt(number) = c * c, and by thinking about how multiplication behaves, we can conclude that either a or b must always be lesser or equal to while the other must be greater or equal to c, because when either a or b is smaller than c the total product would shrink unless the other one grows to counteract this fact.
   The next problem is your use of a boolean array, which is completely redundant. You do not need to store the result of the division test for each number separately, but you only have to keep track of whether you have found a divisor for number (=> number is not prime) or not (=> number is prime). All in all, I would rewrite the method to something like this:

   public static boolean checkIfPrime(int number) {
       if (number < 2) {
           return false;
       }
   
       if (number == 2) {
           return true;
       }
   
       int root = (int) Math.sqrt(number);
       for (int i = 2; i <= root; i++) {
           if (number % i == 0) {
               return false;
           }
       }
   
       return true;
   }
   

---

Although this code should be reasonably efficient for relatively small numbers, there are faster algorithms to solve this problem. However, most of these are not as easy to implement, and if you are not planning on doing this for very large integers, then you should be fine with the changes I suggested. If you are still interested in improving effiency, I point you to the Wikipedia article about the prime-counting function for a start.

Answer 2

Consider

// If number is prime -> return true
public static boolean isPrime(int number) {
    if (number == 2) {
        return true;
    }

    if (number < 2 || number % 2 == 0) {
        return false;
    }

    for (int i = 3, n = 1 + (int)Math.sqrt(number); i <= n; i += 2) {
        if (number % i == 0) {
            return false;
        }
    }

    return true;
}

Putting comments on separate lines makes it easier to see that they exist when quickly scanning the code. And in this case, it avoids unnecessary scrolling.

Boolean methods in Java are normally named isSomething or hasSomething.

The only even prime is 2. If we eliminate that first, then we can check for numbers less than 2 or divisible by 2 at the same time.

We don't need the prim variable, as we can return false as soon as we find a reason. If we get to the end, we can return true. This has the same effect as your code with less scaffolding.

Since we've already checked for even numbers, we only need to check odd numbers in the for loop.

If you can multiply two factors to get a product, at least one of the factors must be less than or equal to the square root of the number. You can see this by trying to multiply two numbers greater than the square root together. If everything is positive, the product will be greater than the target number. So once we've checked the square root, we don't need to keep going. If there was a pair, we'd already have found half of it.

We could tweak the isPrime method a little more and likely make it a little faster. However, we have other options that don't require isPrime at all.

Sieve of Eratosthenes

If you know the maximum number that you have to check and need to check many numbers, consider using the Sieve of Eratosthenes or similar. That's the most efficient way to find all the primes in a range. So you'd first find all the primes and then just query a data structure thereafter.

There are a number of implementations on this site.

In this case, you could have a method countPrimesUnder that would iterate over the data structure and count the primes.