return an array of prime numbers

Question

I need a method to return prime numbers in an array.

So if given: primeArray(5)

than an array like so should be returned: (2, 3, 5)

For some reason this doesn't seem to work for me:

public static int[] primeArray(int numFind)
{
    //determines the size of the array returned
    int primeTotal = 0;

    //loop to find total prime numbers
    for (int j = 1; j <= numFind; j ++)
    {
        if (isPrime(j))
        primeTotal +=1;
    }

    //declare array to be returned
    int[] numA = new int[primeTotal];

    //current index of prime number
    int iP = 0;

    //loop to add prime elements to array
    for (int x = 1; x <= numFind; x ++)
    {
        if (isPrime(x))
        {
            numA[iP]=x;
            iP++;    // <--- THIS IS CAUSING ME PROBLEMS
        }

    }

    return numA;
}

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

This is what I'm using to test my code:

    int[] num = primeArray(11);

    System.out.println(num[0]);
    System.out.println(num[1]);

But for output I'm getting this:

1 
2

If however I comment out the iP++; than the if statement finally decides to execute ONLY when prime numbers are passed as a parameter in: isPrime(j) but then if defeats the whole purpose of the primeArray method because I need the primeArray method to return an array of prime numbers.

Answer 1

Your isPrime() method is faulty. You need to return false, for number < 2. Also, you don't need to iterate till n, just iterate till n / 2 or even better sqrt(n).

Change it to:

public static boolean isPrime(int n) {

    if (n < 2) return false;

    int maxIteration = Math.ceil(Math.sqrt(n));

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

    return true;
}

Now, given your real problem (Note that your method is just fine. It would return you correct result, given you changed your isPrime() method), but you can avoid iterating twice by using an ArrayList instead of array:

List<Integer> primes = new ArrayList<Integer>();

//loop to find total prime numbers
for (int j = 1; j <= numFind; j ++)
{
    if (isPrime(j))
        primes.add(j);
}

And then you can just return primes, and change the return type of method to List<Integer> instead of int[].

public static List<Integer> primeNumberList(int numFind)

If you really want to return an int[], then you need to do some work converting the ArrayList to an int array. I leave this task to you. Just search for this on SO only, you will get too many posts.

---

Also, if you are going to generate all prime numbers till a very large number, then you should take a look at Sieve of Eratosthenes