Java Program to Implement Wheel Sieve to Generate Prime Numbers

This is java program to implement Wheel Seive method to generate the prime numbers from 2 to the given limit. This algorithm reduces the time by checking only till n^2.

Here is the source code of the Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a sample program to print all the prime numbers between 2 and n
  2. import java.util.LinkedList;
  3. import java.util.Scanner;
  4.  
  5. public class Sieve_Method
  6. {
  7.     public static LinkedList<Integer> sieve(int n)
  8.     {
  9.         if(n < 2) 
  10.             return new LinkedList<Integer>();
  11.  
  12.         LinkedList<Integer> primes = new LinkedList<Integer>();
  13.         LinkedList<Integer> nums = new LinkedList<Integer>();
  14.  
  15.         for(int i = 2;i <= n;i++)
  16.         { //unoptimized
  17.             nums.add(i);
  18.         }
  19.  
  20.         while(nums.size() > 0)
  21.         {
  22.             int nextPrime = nums.remove();
  23.             for(int i = nextPrime * nextPrime;i <= n;i += nextPrime)
  24.             {
  25.                 nums.removeFirstOccurrence(i);
  26.             }
  27.             primes.add(nextPrime);
  28.         }
  29.         return primes;
  30.     }
  31.     public static void main(String args[])
  32.     {
  33.         System.out.println("Enter the upper bound : ");
  34.         Scanner sc = new Scanner(System.in);
  35.         int end = sc.nextInt();
  36.  
  37.         System.out.println(sieve(end));
  38.         sc.close();
  39.  
  40.     }
  41. }

Output:

$ javac Sieve_Method.java
$ java Sieve_Method
Enter the upper bound : 
70
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.