Sieve Of Erastothenes using Java

Question

have started learning Java recently and was looking into some easy algorithms. I found the Sieve Of Erastothenes algorithm here

I am trying to get better at writing good code for my solutions. Please give me your suggestions.

import java.util.Scanner;

public class SieveofErastothenes {

    public static void main(String[] args) {

        Scanner keyboard = new Scanner(System.in);
        System.out.println("Enter the prime number ceiling");
        int ceiling = keyboard.nextInt();
        keyboard.close();
        prime(ceiling);

    }

    private static void prime(int n) {

        // create an array with 0 and 1 where 1= Prime and 0= Non Prime
        int[] isPrime = new int[n + 1];
        // set all values to 1
        for (int i = 2; i <= n; i++) {
            isPrime[i] = 1;

        }

        int upperbound = (int) Math.sqrt(n);
        for (int i = 2; i <= upperbound; i++) {
            if (isPrime[i] == 1) {
                for (int j = 2; j * i <= n; j++) {
                    isPrime[j * i] = 0;
                }
            }
        }

        printprime(isPrime, n);

    }

    private static void printprime(int[] isPrime, int n) {
        for (int i = 0; i <= n; i++) {
            if (isPrime[i] == 1) {
                System.out.println(i);

            }
        }


    }
}

A few online tutorials use a boolean array to set all the values as true or false whereas I am using an integer array and setting the values to 0 and 1 initially.Does this make any difference in the performance?

Answer 1

The short answer to your question, is yes. It does make a difference to performance. However, we're only talking about increased RAM usage (integer datatype is bigger than boolean) - and we're talking about a lot less than 1kb.

So on a modern computer (even a Raspberry Pi), you won't have a problem.

Now, general advice & tips...

1. Variable names should be appropriate to their use. When I see isPrime I assume that it's a boolean value (because it's either a prime or it isn't). Regardless of performance impact, boolean makes more sense because you only ever set 0 or 1.
2. Loops - is there a specific requirement why you appear to be writing 1.3 compliant code? For loops could be done with the for( TYPE var : collection) form. Makes it more readable IMO - I don't need to worry about the control variable being tampered with during loop execution.
3. Method names - should be descriptive, and use camel case. prime() and printprime are examples of how not to do it.
4. Math.sqrt() takes a double and returns a double - why are you casting directly to int? If you really want an int datatype, you should be rounding as appropriate (up vs down). Get out of the habit of just casting primitives before you move on to their wrappers - eg, you cannot cast Double directly to int.
5. Comments - opinions vary. Use sparingly and only when deliberately against accepted convention, or to explain why you have to do something a certain way even though you know it should be done differently. JavaDoc comments again, should be used sparingly. Get the class & method names right, and JavaDoc shouldn't be needed. There could be constraints that would push you to use JavaDoc, and if so, that's fine.
6. Unit test. Unit test. Unit test. You don't appear to have any. Write the Unit Tests before you write your main code. Write as little main code as possible to make your unit tests pass (make sure your Unit Tests are appropriate for requirements first).

Answer 2

It does indeed make a difference whether you use bool[] or int[] - an int uses four times as much memory and hence the array requires four times as many cache line transfers as bool does, and it will exceed the CPU's level-1 cache capacity - usually around 32 KiByte - for smaller values of n than a boolean array. And, as Dave said, testing the truthiness of a bool cell looks nicer in languages where integers aren't truthy and thus need to be compared to 0, and it reflects the program logic better.

If you invert the logic of your sieve from 'is prime' to 'is composite' then you can skip the initialisation of the array to all true (or 1) because the array will already have been initialised to the bit pattern 0, and semantically it would be more accurate anyway. Besides, I don't think that the old Greek ever said anything about marking all numbers as 'prime' before the start of the sieving - that must have been invented by tutors in the modern age.

Also, the Sieve of Eratosthenes has no need for multiplying indices - it strides additively, by adding the current prime to the current position during each step:

for (int i = 2, sqrt_n = (int)Math.sqrt(n); i <= sqrt_n; ++i)
    if (!is_composite[i])
        for (int j = i * i; j <= n; j += i)
            is_composite[j] = true;

I've also adjusted the starting point for the crossing-off to the square of the current prime, since all smaller multiples will already have been crossed off during the cycles for smaller primes.

The outer loop still contains a small inefficiency: there is only one even prime, yet the loop tests all even numbers up to sqrt(n) for compositeness. Quite a few performance reserves can be unlocked by removing the number 2 from the picture entirely and sieving only the odd numbers. The biggest gain comes from removing half of all 'hops' (crossings-off) in the inner loop and from the halved memory pressure.

Last but not least, the performance will drop significantly when the sieve array gets appreciably bigger than the L1 cache size of the CPU (typically 32 KiByte), and it will drop even further when the L2 cache size is exceeded. If you need decent performance in ranges beyond the L1 cache size then you might want to consider segmented sieving, i.e. working the sieve range in cache-sized blocks.

This is quite simple to implement, and definitely simpler than windowed sieving; you can find an example in my answer to Find prime positioned prime number. There you can also see that odds-only sieving is just as simple as plain sieving; it just requires a bit of care when dealing with indexes (i.e. clarity whether a given value is supposed to be a number or a bit index).

Many coding challenges that deal with primes require the sieving of millions of numbers instead of small handfuls, and so an investment in studying suitable 'prime technology' can pay off handsomely. Moreover, this study can tell you lot about the efficiency of basic mechanisms in your language - be it bool[] vs BitSet (bool[] wins hands-down in Java, C# and C++, if you have an eye on cache sizes), or the performance cost of syntactic sugar.

Answer 3

A few online tutorials use a boolean array to set all the values as true or false whereas I am using an integer array and setting the values to 0 and 1 initially.Does this make any difference in the performance?

You would need to profile it (it will probably depend on the virtual machine used).

But regarding readability, boolean makes a lot more sense. A number is either prime, or it is not (there is no "maybe prime" here). true has a real meaning here (is prime? true), while 1 does not; it is only understandable via comments or convention.

Using boolean also makes your ifs nicer. if (isPrime[j]) is quite nice to read and easy to understand, while isPrime[i] == 1 is not.

Misc

• you can use Arrays.fill to initialize your array.
• your function should not print the primes itself, but return them instead (just an array of prime numbers, not the whole isPrime array). That way, it's easily testable and reusable.
• then, your function could be called getPrimes, which makes it more obvious what the function does.