Find prime number in certain range

Question

I need the program to find the prime numbers and put them in an array and return them. I only want to use System.out in the Main class. What should I add to my code? Thanks.

This is my first method in the first class to find which numbers are prime:

private boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }

    return true;
}

This is the other method that I need help with:

public int[] test(int a, int b) {
    //what do I write here
    for (int i = a; i <= b; i++) {
        if (isPrime(i)) {
            //what do I write here, I only want to use syso in the other
            //class(Main).
        }
    }

    return ?;
}

And this is my main Class:

public static void main(String... args) {
    Prime p = new Prime();
    System.out.println(p.test(10, 30));
}

Answer 1

put the number in a list and convert it to an int array:

public int[] test(int a, int b) {
    List<Integer> result = new ArrayList<>();
    //what do I write here
    for (int i = a; i <= b; i++) {
        if (isPrime(i))
            result.add(i);
            //what do I write here, I only want to use syso in the other
                            //class(Main).
    }
    return result.stream()
            .mapToInt(Integer::intValue)
            .toArray();
}

Answer 2

public class Prime {

    public static void main(String... args) throws IOException {
        System.out.println(Arrays.toString(getPrimesWithin(10, 30)));
    }

    public static int[] getPrimesWithin(int lo, int hi) {
        return IntStream.rangeClosed(lo, hi)
                        .filter(Prime::isPrime)
                        .toArray();
    }

    private static boolean isPrime(int val) {
        if (val < 2)
            return false;

        for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
            if (val % i == 0)
                return false;

        return true;
    }

}

Answer 3

This changes the test method return type an ArrayList, but if that's acceptable, this could work:

import java.util.ArrayList;

class Main {
  public static void main(String[] args) {
    Prime p = new Prime();
    System.out.println(p.test(10, 30).toString());
  }
}

class Prime {
  public ArrayList<Integer> test(int a, int b) {
    ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
    for (int i = a; i <= b; i++) {
      if (isPrime(i)) {
        primeNumbers.add(i);
      }
    }
    return primeNumbers;
  }

  private boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
      if (n % i == 0)
        return false;
    }

    return true;
  }
}

Answer 4

Your test() method is of return type int[] but you do not know how many prime numbers you'll be getting in response. Basically you don't know the size of array so instead of using array, use ArrayList from java.util package. Create an object of List and add all your prime numbers in it and return that. Then in the main() method, collect your response of test() method in any variable and then iterate over it to print the result.

Below is the code to do that -

test() Method :

public List<Integer> test(int a, int b) {
  List<Integer> primeNumbersList = new ArrayList<Integer>();
  for (int i = a; i <= b; i++) {
    if (isPrime(i)){
      primeNumbersList.add(i);
    }          
  }
        return ?;
}

main() method :

public class Main {

    public static void main(String[] args) {
        Prime p = new Prime();
        List<Integer> primeNumbers = p.test(10,30);
        foreach(int num : primeNumbers){
          System.out.println(num);
        }
    }
}

Answer 5

In main use this to print array: Arrays.toString(p.test(10, 30))

in test method collect all prime numbers into array and return that array

public int[] test(int a, int b) {
    List<Integer> list = new ArrayList<>();
    for (int i = a; i <= b; i++) {
        if (isPrime(i))
            list.add(i);
    }

    int c = 0;
    int[] result = new int[list.size()];
    for(int e : list) {
        result[c++] = e;
    }
    return result;
}

public static void main(String[] args) {

    Prime p = new Prime();
    System.out.println(Arrays.toString(p.test(20, 100)));

}

Answer 6

There are several optimizations can be done while caluculating prime numbers:

• Not every Number is Prime

The only even number among primes is 2 (so we can eliminate all even numbers apart from 2). And there's no gap between the prime, which is 3.

I.e. we can omit 4 of every 6 consecutive numbers, without checking them. I.e. candidate number can be represented as N * 6 - 1 and N * 6 + 1, which are guaranteed not to be divisible neither by 2, no by 3.

• Use square root as a boundary

If the number is prime, it's fruitless to check it against numbers greater than its square root (see elaborate explanation here).

Here's how isPrime() check can be implemented taking into consideration both optimizations listed above

public static boolean isPrime(int candidate) {
    if (candidate == 2 || candidate == 3) return true;
    if (candidate % 2 == 0 || candidate % 3 == 0) return false;

    boolean isPrime = true;
    for (int i = 6; i <= Math.sqrt(candidate); i += 6) {
        if (candidate % (i - 1) == 0 || candidate % (i + 1) == 0) {
            isPrime = false;
            break;
        }
    }
    return candidate > 1 && isPrime;
}

• Don't recalculate the same Primes

Validate the potential prime number against the primes that has been already discovered.

Here's my implementation created based on all the principles listed above, which allow to calculating primes in the given range in a highly performant manner encapsulated into a separate utility class.

public class PrimesGenerator {
    
    private final List<Integer> primes;
    private final int loBound;
    private final int hiBound;

    private PrimesGenerator(int loBound, int hiBound) {
        this.primes = new ArrayList<>();
        this.loBound = loBound;
        this.hiBound = hiBound;
    }

    public static PrimesGenerator getInstance(int loBound, int hiBound) {
        PrimesGenerator generator = new PrimesGenerator(max(loBound, 2), hiBound);
        generator.init();
        return generator;
    }

    private void init() {
        if (loBound <= 2) primes.add(2);
        if (loBound <= 3) primes.add(3);

        int candidate = 5;
        while (candidate <= hiBound) {
            if (isPrime(candidate)) {
                primes.add(candidate);
            }
            candidate = getNextCandidate(candidate);
        }
    }

    private boolean isPrime(int candidate) {
        boolean isPrime = true;
        double sqrt = sqrt(candidate);
        for (int i = 0; i < primes.size() && primes.get(i) <= sqrt; i++) {
            if (candidate % primes.get(i) == 0) {
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }

    private int getNextCandidate(int candidate) {
        return candidate % 6 == 5 ? candidate + 2 : candidate + 4;
    }

    public List<Integer> getResult() {
        return primes.stream()
                .dropWhile(i -> i < loBound)
                .collect(toUnmodifiableList());
    }
}

Usage example:

public static void main(String[] args) {
    PrimesGenerator generator = PrimesGenerator.getInstance(2,100);
    List<Integer> primes = generator.getResult();
    System.out.println(primes);
}

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]