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.
- Check whether the “numbers” is not empty.
- 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.”
- Remove the value.
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]
Want to see more full solutions like this?
Chapter 11 Solutions
Building Java Programs: A Back To Basics Approach (5th Edition)
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education