Prime Number Generator Logic

Question

I am supposed to make a class PrimeNumberGenerator which has a method nextPrime that will print out all prime numbers up to a number the user inputs.

Ex)

Enter a Number: 
20
2
3
5
7
11
13
17
19

Our teacher told us that we should use a nested for loop. I tried, but when I tried to make the inner (nested) loop, I got really confused.

Here is my code: (I'm going to make a tester class later)

public class PrimeGenerator {

    private int num;
    boolean isPrime;

    public PrimeGenerator(int n)
    {
        num = n;
    }

    public int nextPrime (int num)
    {
        for (int i=2; i < num; i++) // The first prime number is 2 and the prime numbers only have to go up to a number the user inputs. 
        {
            for (int j = 3; j<=i/2; j+=2) // The next prime number is 3 and I attempted to loop through to get the next odd number.
            {
                if (num % i == 0) //if the number (upper limit) mod a "prime number" is 0, then that means that number is not really "prime" after all. 
                {
                    break;
                }
            }
        }

        return num;
    }

}

Answer 1

There are two questions here that you have forgotten to ask:

• Why does the nested loop make everything so complicated?
• What can I do to uncomplicate things again?

So let's play along with the question you actually asked, and then answer the first two questions.

What you want to do can probably be described as such: For every number, 1-n, where n is input by the user, print it if it's prime.

Okay, so let's write up the pseudocode/logic here. It looks like Java, but it isn't. It's just meant to convey what we're going for:

int largestNumber = readIntegerFromKeyboard();

for all ints i from 1 to largestNumber {
    if(isPrime(i)) {
        println(i);
    }
}

So let's do this! But first, we need a laundry-list of all the things we need to do:

• read integer from keyboard
• loop over numbers
• check if the number is a prime
• print primes (with newlines)

Let's just do the two easy things first. Reading the input and setting up the loop:

Scanner keyboard = new Scanner(System.in);
int largestNumber = keyboard.nextInt();

for(int i = 1; i <= largestNumber; ++i) {
    if(isPrime(i)) {
        System.out.println(i);
    }
}    

keyboard.close();

Okay, that seems simple enough. So far, everything here makes sense. It's easy to understand the logic. Now however, when we replace isPrime with actual logic, everything is about to get cluttered and hard to read.

So let's write this code as easy to understand as possible. We will use no tricks to speed up the code. Readability and correctness are the only two things we will care about. We will use the modulo operator to check if something is evenly dividable. Modulo is like integer division, except that it returns the remainder and not the result. so 7 / 2 = 2. 7 % 2 = 1, because there's one left over.

Scanner keyboard = new Scanner(System.in);
int largestNumber = keyboard.nextInt();

for(int i = 1; i <= largestNumber; ++i) {
    // checks if the number is a prime or not
    boolean isPrime = true;
    for(int check = 2; check < i; ++check) {
        if(i % check == 0) {
            isPrime = false;
        }
    }
    if(isPrime) {
        System.out.println(i);
    }
}    

So the good news is, this works. The bad news is, this is harder to read than necessary. And it's not a lot we can do here. When I wrote this up, I made several stupid mistakes, mixing up the variables. Maybe I'm stupid. So maybe I should in that case write stupid-proof code. ;) You on the other hand is not stupid. But you may work with me, who is stupid, so you kind of have to write stupid-proof code yourself, so that you can productively work with me.

The big problem is that we have this massive loop in the middle of the other loop. This is what tripped me up. I referred to the wrong loop variable. But why do we need a loop in a loop? Wasn't it much more comfortable to read:

if(isPrime(i)) {
    System.out.println(i);
}

Instead of that whole mess? Your professor pointed out the nested loops. But it threw you off. Instead, just write the isPrime method. And the fact is, that this is true for every single instance of nested loops I have ever come across.. So let's see how that would look instead:

class Homework {
    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int largestNumber = keyboard.nextInt();

        for(int i = 1; i <= largestNumber; ++i) {
            if(isPrime(i)) {
                System.out.println(i);
            }
        }
        keyboard.close();
    }

    /**
     * Checks is a positive integer is a prime number
     */
    public static boolean isPrime(int number) {
        for(int check = 2; check < number; ++check) {
            if(number % check == 0) {
                return false;
            }
        }
        return true;
    }
}

That to me is a whole lot easier to read. Not because the logic got easier, but because the only thing I had to care about was either:

• Checking all the numbers and printing the correct ones, or
• how to check that a number is a prime.

Since these two separate things are now apart, you have much less to think about at once. Rejoice, for you have just done a proper abstraction. This makes your code easier to understand, because it separates out the two concerns. This is a key way of making larger projects. You take difficult things and do them by themselves. Then you can test them by themselves, and use them by themselves.

(Now I only have to await the downvotes for answering a question you didn't explicitly ask...)

Answer 2

I know the question is for a while out here but since no one posted java8/stream approach solution, here is one of the possible ways.

Gist can be forked here.

Print output: [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

import java.util.*;
import java.util.stream.Stream;

import static java.util.stream.Collectors.toList;


public class PrimeNumber {

     /**
     * Java 8 / Lambda approach to generate Prime number.
     * Prime always start to look from number 1.
     * @param series Number of how many Prime number should be generated
     * @return List holding resulting Prime number.
     */
    public static List<Integer> generate(int series) {
        Set<Integer> set = new TreeSet<>();
        return Stream.iterate(1, i -> ++i)
                .filter(i -> i %2 != 0)
                .filter(i -> {
                    set.add(i);
                    return 0 == set.stream()
                            .filter(p -> p != 1)
                            .filter(p -> !Objects.equals(p, i))
                            .filter(p -> i % p == 0)
                            .count();
                })
                .limit(series)
                .collect(toList());
    }

    // Let's test it!
    public static void main(String[] args) {
        List<Integer> generate = PrimeNumber.generate(20);
        System.out.println(generate);
    }
}