2
\$\begingroup\$

I wanted to create a program that lists all prime numbers to a given upper bound and that will also provide the amount of primes in the set. After many hours of trial and error I was able to solve it.

I am sure this is not efficient and I want to learn how to look at code and see where improvements can be made. Or just to simply improve my computational thinking.

For instance, would it be better to not put this in an ArrayList?

Thanks in advance.

//Program should be able to print all primes between 1 and a given number and should also provide the amount of primes for the given set. 

public class NewPrimes {
    
    //Method to loop a value and to determine if the number is a prime. 
    public static void primes (int upperBound) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        for (int i = 2; i <= upperBound; i++) {
            if (i == 2) {
                arr.add(2);
            }
            for (int x = 2;(x < i) && (i % x != 0); x++) {
                if (x == i - 1) {
                    arr.add(i);
                }
            }
        }
        System.out.println(arr);
        System.out.println(arr.size());
        
    }
    

    public static void main(String[] args) {
        NewPrimes.primes(1000);
        NewPrimes.primes(100);
        NewPrimes.primes(10000);        
    }
}
\$\endgroup\$
2
  • 3
    \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question? for examples, and revise the title accordingly. \$\endgroup\$
    – Martin R
    Commented Mar 10, 2022 at 20:41
  • \$\begingroup\$ HI @Lax .. Apart from 2, no even number will ever be a prime - so you're doing twice as much work as needed (without even looking beyond the first line of the algorithm). AND even if you want to ignore the primes you've already got (in arr), you never need to check more than i/2.. \$\endgroup\$
    – Mr R
    Commented Mar 11, 2022 at 1:23

3 Answers 3

4
\$\begingroup\$

Separation of concerns

At present, the two functions of this program (finding prime numbers and printing them) are combined into one Java function. That makes it hard to re-use the code for anything else. Consider writing a function that returns a list of primes and a separate one that knows how to print the list and its length.

Remembering results

When we call NewPrimes.primes(100), having previously called NewPrimes.primes(1000), the code shouldn't need to do any additional work. We have already found all of those primes under 100, and it's pointless to do it all again. If we remember (as an instance member), all the primes we've found so far, we could return a subset of those in the second call.

Similarly, when NewPrimes.primes(10000) is called, we can reuse the primes under 1000, and only need to generate those in the range 1000-10000 to append to the list.

Algorithm

Finding primes by trial division (i % x != 0) is the most computationally expensive method to discover them. It's a topic that's already covered well enough elsewhere that it doesn't make sense to describe more efficient methods in an answer here - you should probably start by reading about prime number sieves, and studying in particular:

\$\endgroup\$
1
\$\begingroup\$

Toby has made some important points - definitely things you should look into - but didn't really give you a review of your code. Let's do that now.

Naming

What is NewPrimes? I don't think prime numbers are anything new, so perhaps you should just call this class Primes, or perhaps PrimeNumberGenerator or something.

upperBound is a bumpyWord. In Java, those are often used for members. A parameter or local variable is usually in snake_case, so this would be better named upper_bound.

arr is very vague. Ok, arr is an array, but an array of what? Is it really an array? An ArrayList<?> can be assigned to a List<?> variable, so maybe it shouldn't be called an array at all. Maybe prime_numbers?

i can be ok for very tight loops, but for larger loops spanning multiple lines, it will help to name the variable to something more significant. In this case, you might be executing arr.add(i), so i really is a prime candidate ... maybe call it candidate?

Similarly, x is used as trial divisors, so perhaps call it divisor? Remember, Java is a compiled language, which means the length of the variable names does not impact the speed of execution at all. Be descriptive. trial_divisor might be better, although it is a bit verbose.

Move one-off's of out loops

        for (int i = 2; i <= upperBound; i++) {
            if (i == 2) {
                arr.add(2);
            }
            ...
        }

How many times is i == 2 tested? Once for each value between 2 and upperBound? How many times will the test evaluate to true? Only once? The first time? How much wasted work is being done?

Instead, write the code like:

        arr.add(2);
        for (int i = 2; i <= upperBound; i++) {
            ...
        }

Moving the if body out of the loop means we don't even need the if statement at all.


            for (int x = 2;(x < i) && (i % x != 0); x++) {
                if (x == i - 1) {
                    arr.add(i);
                }
            }

I hate this with a passion. Like the outer loop, x == i - 1 can only be true once, on the last iteration, yet it is tested every time the loop executes. However, x is local to the loop, so you can't test it outside the loop. We need a variable which survives the length of the loop to indicate whether we found a factor or not. Let's re-write the loop using one:

            bool is_prime = true;
            for(int divisor = 2; divisor < candidate; trial_divisor++) {
                if (candidate % divisor == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                prime_numbers.add(candidate);
            }

Except, we've introduced a bug. This loop will declare the 2 is prime (which it is) and add it to prime_numbers, but we've already added it as a special case. Either start the candidate loop at 3 (and only check odd candidates) or remove the special case!

Efficiency

When it comes time to check if 221 is prime, you try dividing it by 2, then 3, then 4, then 5, then 6, then 7, then 8, then 9, then 10, then 11, then 12, and then 13 (which you discover is a factor of 221).

  • There was no need to try dividing by 4, since you already tried dividing by 2.
  • There was no need to try dividing by 6, since you already tried dividing by 2 and 3.
  • There was no need to try dividing by 8, since you already tried dividing by 2 and 4.
  • There was no need to try dividing by 9, since you already tried dividing by 3.
  • There was no need to try dividing by 10, since you already tried dividing by 2 and 5.
  • There was no need to try dividing by 12, since you already tried dividing by 2, 3, 4, and 6.

In short, you only needed to try dividing by 2, 3, 5, 7, 11, and finally 13 ... that is, you need to try dividing by only the prime numbers. If only you had a list of prime numbers you could use. Oh wait! You're generation one!

            bool is_prime = true;
            for(int divisor: prime_numbers) {
                if (candidate % divisor == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                prime_numbers.add(candidate);
            }

Reworked Code

Applying the above suggestions, as well as some of Toby's, you might get:

public class Primes {
    
    public static List<Integer> generate_primes(int upper_bound) {
        var prime_numbers = new ArrayList<Integer>();
        
        prime_numbers.add(2);
        for (int candidate = 3; candidate <= upper_bound; candidate += 2) {
            bool is_prime = true;
            for (int divisor: prime_numbers) {
                if (candidate % divisor == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                prime_numbers.add(candidate);
            }
        }
        return prime_numbers;
    }

    public static void generate_and_print_primes(int upper_bound) {
        var primes = generate_primes(upper_bound);
        System.out.println(primes);
        System.out.println(primes.size());
    }

    public static void main(String[] args) {
        generate_and_print_primes(1_000);
        generate_and_print_primes(100);
        generate_and_print_primes(10_000);
    }
}

This is arguably better, but there is still plenty of room for improvement. When checking if 199 is prime, and one can stop at \$\sqrt{199}\$, since no factor can be larger than that without a corresponding factor smaller than that. This eliminates the need for checking if 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, or 197 are divisors of 199. Simply break out of the loop when divisor * divisor > candidate. However, the sieves and wheels linked in Toby's answer offer still better performance.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ It's quite unusual for Java code conventions to recommend snake_case naming for variables. Upper snake case is often suggested for constants: static final int MAX_VALUE = 5; \$\endgroup\$
    – TomG
    Commented Mar 12, 2022 at 10:10
1
\$\begingroup\$
        for (int i = 2; i <= upperBound; i++) {
            if (i == 2) {
                arr.add(2);
            }
            for (int x = 2;(x < i) && (i % x != 0); x++) {
                if (x == i - 1) {
                    arr.add(i);
                }
            }
        }

This seems awfully complicated. First, we can pull

            if (i == 2) {
                arr.add(2);
            }

out of the loop as

            if (upperBound >= 2) {
                primes.add(2);
            }

That saves us one check per loop iteration at the cost of doing one check outside the loop.

I would find primes much more descriptive than arr.

Second, we can cut the number of tests in half by only checking the odd numbers.

        for (int i = 3; i <= upperBound; i += 2) {

Third, the inner loop does way more checks than necessary. Consider

            for (int prime : primes) {
                if (i / prime < prime) {
                    primes.add(i);
                    break;
                }

                if (i % prime == 0) {
                    break;
                }
            }

This only checks if primes are factors.

We can stop once we've checked up through the square root. At least one of any factor pair must be less than or equal to the square root.

Note that this keeps your original algorithm and just improves it. As already noted, there are alternative algorithms that are better for this specific problem.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.