Java function to find prime number not working

Question

The function takes in an integer N. The function must print all prime numbers from 2 to N (including N, if N is itself a prime number).

I have the function and it runs, but it is skipping some prime numbers and even including some even numbers like 8. I can't seem to find the bug that is causing this.

Here's what my code looks like:

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


public class PrimeNumbers {

    List <Integer> primeList = new ArrayList<Integer>();
    public ArrayList<Integer> findPrimes(int n){

        if(n == 2){
            primeList.add(n);
        }
        else{
            //should I have i=i+2 instead of i++ to move faster? 
           //If so, by doing this, it causes weird and different 
          //output when running
            for(int i=2; i<=n; i++){
                if(n%i != 0){
                    primeList.add(i);
                }
            }

        }

        return (ArrayList<Integer>) primeList;
    }

    public static void main(String[] args) {
        PrimeNumbers pn = new PrimeNumbers();

        System.out.println(pn.findPrimes(15));
    }

}

Answer 1

Your logic for finding prime numbers is incorrect.

Right now, what your code does is: 1. Iterate on all the integers up to N 2. Find any integer that N can't be divided by, and add them to the list. This has nothing to do with prime numbers.

Instead, your code should do something like: 1. Iterate on all the integers up to N 2. For each of these integers (let's say M), run a sub-loop iterating on all integers below it, and checking if none of those integers can divide M. If the sub-loop finishes without finding a divider of M, add M to the list - it's a prime number (can't be divided by any integer except 1 and itself).

Simple code for checking if a number (2 or above) is prime:

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

    return true;
}

There are many optimisations for this and it's a world by itself.

Answer 2

Your logic is entirely backwards. You can only say a number is prime if you've tested ALL possible divisors. You're currently adding ANY number which has a non-zero remainder, which is BACKWARDS. A non-zero remainder means it was NOT evenly divisible, meaning it's NOT a multiple of the factor you're testing, e.g.

8 % 3 -> 2
2 != 0 -> true
therefore 8 is prime

You can only do your .add() call AFTER you've finished the loop and no tests came back true:

is_prime = true; // assume prime
for(i = 2; i <= n; i++) {
     if (n % 2 == 0) { // no remainder, even divisible, therefore NOT primt
         is_prime = false;
         break; // abort the loop, no point in testing more
     }
}

And yes, you can boost efficiency somewhat by starting your tests at 3 and jumping by 2. Since 2 is the only even prime, it is literally impossible for any OTHER even number to be prime, because 2 is a divisor of all even numbers. So test 3,5,7,9,etc...

e.g.

  test if `n` is even and `!= 2` - if so, then it's NOT prime
  run 3,5,7,... loop to test everything else

Answer 3

All you've done is find the not factors of n. You test if each number leading up to it is a factor of n by adding it if n % i != 0.

What you need to do is iterate from 2 to n, and for each of those numbers, test if it's prime. You will need two loops. I suggest creating a method to determine prime numbers, and I guess your current method is find as it is. Just replace if (n % i != 0) with if(isPrime(i))

public static boolean isPrime(long n) {
    // eliminate the simple cases
    if (n < 2) {
        return false;
    } else if (n == 2) {
        return true;
    }

    // only test up until the square root of that number
    for (int i = 2; i < Math.pow(n, 0.5) + 1; i++) {
        if (n % i == 0) {
            return false; // found a factor, it's not prime
        }
    }
    return true; // hasn't found a factor and returned false, so it's prime
}

And then in your current code:

for(int i=2; i<=n; i++){
    if(n%i != 0){
        primeList.add(i);
    }
}

Just change if(n%i != 0){ to if(isPrime(i))

So it would be this:

for(int i=2; i<=n; i++){
    if(isPrime(i)) {
        primeList.add(i);
    }
}