Chapter 11, Problem 1E

Explanation of Solution

Modified “Sieve()” program to make required two optimizations:

//Import required packages

import java.io.File;

import java.io.FileNotFoundException;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Scanner;

//Definition of class Test

public class Sieve {

    //Definition of main class

    public static void main(String[] args)

    {

        //Print the statement

System.out.println("This program will tell you all prime" );

System.out.println( "numbers up to a given maximum . ");

        System.out . println() ;

        //Create an object for scanner class

        Scanner console= new Scanner(System. in);

        //Get the integer from the user

        System.out.print( "Maximum number? " );

        int max= console.nextInt() ;

        //Create an object for sieve

        List<Integer> primes= sieve(max) ;

        //Print the result

        System.out.println(primes);

    }

    //Definition of method sieve()

    public static LinkedList<Integer> sieve(int max)

    {

        //Create an object primes for LinkedList

LinkedList<Integer> primes = new LinkedList<Integer>();

        //Create an object numbers for LinkedList

LinkedList<Integer> numbers = new LinkedList<Integer>();

        //Add 2 to the list

        numbers.add(2);

        //Traverse the loop till it reaches max

        for (int i = 3; i <= max; i += 2)

        {

            //Add the values to the "numbers"

            numbers.add(i);

        }

        //Declare the variable sqrt

        double sqrt = Math.sqrt(max);

        //Check whether the numbers is not emppty

        while (!numbers.isEmpty())

        {

// remove a prime number from the front of the list

            int front = numbers.remove(0);

            //Add the front

        primes.add(front);

        //Check whether the front is greater than sqrt

        if (front >= sqrt)

        {

//Check whether the numbers is not empty

            while (!numbers.isEmpty()) {

            //Add the numbers

            primes.add(numbers.remove(0));

        }

    }

        // Create an object for iterator

    Iterator<Integer> itr = numbers.iterator();

    //Check whether itr has value

    while (itr.hasNext())

    {

        //Get the next value and store it in current

        int current = itr.next();

//Check whether "current" mod "front" equals to "0"

        if (current % front == 0)

        {

            //Remove the value

            itr.remove();

        }

        }

    }

    //Return the value of primes

    return primes;

}

}

Explanation:

• Define the static method “sieve()”.
  • Create an object “primes” for the “LinkedList”.
  • Create an object “numbers" for the “LinkedList”.
  • Add “2” to the list.
  • Traverse the loop till it reaches “max”.
    • Add the values to the “numbers”.
  • Declare the variable “sqrt”.
  • Check whether the “numbers” is not empty.
    • Remove a prime number from the “front” of the list.
    • Add the front to “primes”.
  • Check whether the “front” is greater than “sqrt”.
    • Check whether the “numbers” is not empty.
      • Add the numbers.
  • Create an object for iterator.
  • Check whether the “itr” has value.
    • Get the next value and store it in current.
    • Check whether “current” mod “front” equals to “0”.
      • Remove the value.
        • Return the value of “primes.”

Sample Output

Output:

This program will tell you all prime

numbers up to a given maximum .

Maximum number? 45

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]