Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Prime numbers – Sieve of Eratosthenes in Java

farenda 2016-09-02 0

Prime numbers – Sieve of Eratosthenes

A prime number is a natural number with only two divisors: 1 and itself.
In this post we’re going to show how to find prime numbers using Sieve of Eratosthenes and explain how it works.

How it works

  1. Create a boolean array for the numbers you want to verify.
    We create an array with size greater by one to comfortably use index as underlying number.
  2. Initially mark all numbers in the array as primes.
  3. Start sieving from the smallest prime number – 2.
  4. Mark as non primes all multiplies of the current prime.
    Notice that we start the sieve from i*i, because all numbers below have been already sieved. For example, when removing multiplies of 5 we can start from 25, because all lower multiplies of 5 have been removed when 2 and 3 were processed – 5*2 = 2*5 and 5*3 = 3*5.
  5. Repeat with the next prime.
    We don’t have to look for primes above maxPrime, because of reasoning in point 4.
void markComplexNumbers(boolean[] primes) {
    primes[0] = primes[1] = false;
    int maxPrime = (int) Math.sqrt(primes.length);
    for (int i = 2; i <= maxPrime; ++i) {
        if (primes[i]) {
            // remove all multiplies of this prime:
            for (int j = i*i; j < primes.length; j += i) {
                primes[j] = false;
            }
        }
    }
}

Properties of the Sieve of Eratosthenes

  • time complexity is O(n log log n)
  • memory complexity is O(n+1)
  • works great for small (in mathematical sense ;-) ) prime numbers

Complete example

package com.farenda.tutorials.algorithms.primes;

import java.util.Arrays;

public class Sieve {

    public static void main(String[] args) {
        boolean[] primes = findPrimes(101);
        printPrimes(primes);
    }

    public static boolean[] findPrimes(int to) {
        // +1 to have index and number with the same value:
        boolean[] primes = new boolean[to+1];
        Arrays.fill(primes, true);
        markComplexNumbers(primes);
        return primes;
    }

    private static void markComplexNumbers(boolean[] primes) {
        primes[0] = primes[1] = false;
        int maxPrime = (int) Math.sqrt(primes.length);
        for (int i = 2; i <= maxPrime; ++i) {
            if (primes[i]) {
                // remove all multiplies of this prime:
                for (int j = i*i; j < primes.length; j += i) {
                    primes[j] = false;
                }
            }
        }
    }

    private static void printPrimes(boolean[] primes) {
        for (int i = 2; i < primes.length; ++i) {
            if (primes[i]) {
                System.out.print(i + ", ");
            }
        }
    }
}

The above code produces the following output:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
Share with the World!
Categories Algorithms Tags algorithms, java
Previous: Java Singleton – enum implementation
Next: Java create XML using DOM

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2021

sponsored