Sieve Of Erastothenes using Java

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?

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.

StackExchange Code Review Q#125573, answer score: 7