Sieve Of Eratosthenes Algorithm To Generate Prime Numbers Upto 100 Inwards Java

There are many occasions when y'all quest to generate all prime numbers upto a specified integer in addition to ane algorithm which is most oftentimes used to generate prime numbers is Sieve of Eratosthenes. Its an ancient greek algorithm to find all prime numbers upto a given number in addition to named subsequently the famous greek mathematician Eratosthenes. He was the commencement homo to calculate the circumference of earth in addition to every bit good known for working on calendars alongside leap years. H5N1 prime unwrap is a whole unwrap which is either divisible yesteryear 1 or itself e.g. 2, iii in addition to 5. You tin encounter they are non divisible to whatever positive whole integer. In other words, prime unwrap doesn't bring a factor other than 1 or itself. You tin purpose this algorithm to generate prime numbers from 1 to 100 or up-to whatever maximum value. In this tutorial, nosotros volition non alone acquire how Sieve of Eratosthenes algorithm plant but every bit good nosotros volition generate prime numbers using this algorithm in addition to verify whether all unwrap generated are genuinely prime or not.

How Sieve of Eratosthenes Algorithm works

The Sieve of Eratosthenes algorithm is quite simple. You practise an array of larger than 1 yesteryear specified integer, so that index of array stand upwards for the actual integer stored on it. Then y'all start alongside 2, because 0 in addition to 1 are non considered prime.

H5N1 prime number is either divisible yesteryear 1 or yesteryear itself, it doesn't bring whatever other factor. Since 2 is a prime number, nosotros score this every bit prime in addition to cross out all its multiple because they won't move prime, Why? because prime numbers doesn't bring whatever factor other than 1 in addition to if a unwrap is multiple of 2 it way it is divisble yesteryear 2, thence non prime. In guild to cross all numbers which are multiple yesteryear 2, nosotros merely skip our array counter yesteryear 2, which way 2, 4, 6, 8 all are multiples of 2 in addition to they good move crossed. Next unwrap inwards the array is 3, instantly iii is every bit good non divisible yesteryear anyone so its a prime in addition to nosotros score it every bit prime in addition to ane time again crossed out all multiples of iii becasue they won't move prime. In guild to cross out multiples of 3, nosotros skip array counter yesteryear 3, which way 3, 9, 12, fifteen all are crossed. Now, Next unwrap is four but its already crossed because it was multiple of 2 so nosotros skip to adjacent unwrap which is 5. Again v is a prime unwrap so nosotros score it every bit prime in addition to cross out all numbers which are multiple of 5, because they won't move prime every bit they are divisible yesteryear 5. In guild to cross all multiples of 5, nosotros merely growth array counter yesteryear 5, so numbers similar 10, 15, 20, 25 volition move crossed out. We move on this procedure until nosotros arrive at at the foursquare source of given number, because every multiple inwards the array has a prime factor that is less than or equal to the foursquare source of the given number, so nosotros don't bring to cross out multiples of numbers larger than that root. For example, inwards guild to honor all prime numbers betwixt 1 to 100, its plenty to banking concern tally until 10.

Sieve of Eratosthenes Algorithm Implementation inwards Java 

Here is our Java plan to generate prime numbers using Sieve of Eratosthenes Algorithm

import org.junit.Test; import static org.junit.Assert.*;  /**  * This shape Generates prime numbers upto a given boundary using the  * Sieve of Eratosthenes algorithm. In this algorithm, nosotros practise   * an array of integers starting from 2, so honor the commencement uncrossed  * integer, in addition to cross out all its multiple. The procedure is repeated  * until at that topographic point are no to a greater extent than multiples inwards the array.   */ public class PrimeNumberGenerator {      private enum Marker{         CROSSED, UNCROSSED;     }     private static Marker[] crossedOut;     private static int[] primes;          public static int[] generatePrimeNumbersUpto(int limit){         if(limit < 2){             return new int[0];                      }else{             uncrossIntegerUpto(limit);             crossOutMultiples();             putUncrossedIntegersIntoPrimes();             return primes;         }     }          private static void uncrossIntegerUpto(int limit) {        crossedOut = new Marker[limit + 1];        for(int i = 2; i<crossedOut.length; i++){            crossedOut[i] = Marker.UNCROSSED;        }              }          private static void crossOutMultiples() {         int iterationLimit = determineIterationLimit();         for (int i = 2; i<= iterationLimit; i++){             if(notCrossed(i)){                crossOutMultipleOf(i);             }         }              }          private static int determineIterationLimit() {         // Every multiple inwards the array has a prime factor         // that is less than or equal to the foursquare source of         // the array size, so nosotros don't bring to cross out         // multiples of numbers larger than that root.        double iterationLimit = Math.sqrt(crossedOut.length);        return (int) iterationLimit;     }          private static boolean notCrossed(int i) {         return crossedOut[i] == Marker.UNCROSSED;     }           private static void crossOutMultipleOf(int i) {         for(int multiple = 2*i;                 multiple < crossedOut.length;                 multiple += i){             crossedOut[multiple] = Marker.CROSSED;         }              }           private static void putUncrossedIntegersIntoPrimes() {         primes = new int[numberOfUncrossedIntegers()];         for(int j = 0, i = 2; i<crossedOut.length; i++){             if(notCrossed(i)){                 primes[j++] = i;             }         }              }      private static int numberOfUncrossedIntegers() {         int count = 0;         for(int i = 2; i<crossedOut.length; i++){             if(notCrossed(i)){                 count++;             }         }                 return count;     }      }

in addition to hither is unopen to of unit of measurement seek to banking concern tally whether our plan is working properly or not

import static org.junit.Assert.*;  import org.junit.Test;  /**  * Junit seek cases to seek our Sieve of Eratosthenes algorithm   * for generating prime numbers upto a given integer.   * @author WINDOWS 8  *  */ public class PrimeNumberGeneratorTest{          public PrimeNumberGeneratorTest(){         System.out.println("Generator prime numbers using"                 + " Sieve of Eratosthenes algorithm");     }          @Test     public void testPrimes(){         int[] primeUptoZero = PrimeNumberGenerator.generatePrimeNumbersUpto(0);         assertEquals(0, primeUptoZero.length);                  int[] primeUptoTwo = PrimeNumberGenerator.generatePrimeNumbersUpto(2);         assertEquals(1, primeUptoTwo.length);         assertEquals(2, primeUptoTwo[0]);                  int[] primeUptoThree = PrimeNumberGenerator.generatePrimeNumbersUpto(3);         assertEquals(2, primeUptoThree.length);         assertEquals(2, primeUptoThree[0]);         assertEquals(3, primeUptoThree[1]);                  int[] primeUptoHundred = PrimeNumberGenerator.generatePrimeNumbersUpto(100);         assertEquals(25, primeUptoHundred.length);         assertEquals(97, primeUptoHundred[24]);              }          @Test     public void testExhaustive(){         for(int i = 2; i<700; i++){             verifyPrimeList(PrimeNumberGenerator.generatePrimeNumbersUpto(i));         }     }      private void verifyPrimeList(int[] listOfPrimes) {        for(int i = 0; i<listOfPrimes.length; i++){            verifyPrime(listOfPrimes[i]);        }              }      private void verifyPrime(int number) {         for (int factor = 2; factor < number; factor++){             assertTrue(number%factor != 0);         }              } }

in addition to hither is the lawsuit of our Unit test, all passed

That's all virtually how to generate prime numbers upto a specified integer using Sieve of Eratosthenes algorithm. This is a rattling efficient algorithm to generate large unwrap of prime numbers in addition to tin move used to solve complex programming problems where y'all quest an array of prime numbers.


Further Learning
Data Structures in addition to Algorithms: Deep Dive Using Java
solution)

10 Points virtually Array inwards Java? (must know facts)

How to honor top ii maximum on integer array inwards Java? (solution)

Write a method to banking concern tally if ii String are Anagram of each other? (method)

Write a plan to honor commencement non repeated characters from String inwards Java? (program)

How to banking concern tally if a unwrap is binary inwards Java? (answer)

Write a plan to banking concern tally if a unwrap is Prime or not? (solution)

Write a method to count occurrences of  a grapheme inwards String? (Solution)

How to banking concern tally if a unwrap is Armstrong unwrap or not? (solution)

Write a Program take duplicates from array without using Collection API? (program)

How to opposite String inwards Java without using API methods? (Solution)

Write a method to take duplicates from ArrayList inwards Java? (Solution)

Write a plan to banking concern tally if a unwrap is Palindrome or not? (program)

Write a plan to banking concern tally if Array contains duplicate unwrap or not? (Solution)

How to honor Fibonacci sequence upto a given Number? (solution)

How to preclude Deadlock inwards Java? (solution)

How to honor largest prime factor of a unwrap inwards Java? (solution)

How to calculate factorial using recursion inwards Java? (algorithm)

How to declare in addition to initialize ii dimensional array inwards Java? (solution)

Write a plan to honor missing unwrap inwards a sorted array? (algorithm)

How to honor largest in addition to smallest unwrap inwards array? (solution)

How to honor prime factors of an integer inwards Java? (solution)

Write a business office to honor middle chemical ingredient of linked listing inwards ane pass? (solution)

How to solve Producer Consumer Problem inwards Java. (solution)

How to search chemical ingredient inwards array inwards Java? (solution)

How to form array using bubble form algorithm? (algorithm)

How to calculate Sum of Digits of a unwrap inwards Java? (Solution)

Write a Program to Check if a unwrap is Power of Two or not? (program)

Sumber https://javarevisited.blogspot.com/

Share this post