import java.util.LinkedList;
import java.util.Scanner;
/**
* 2:42 - 3:30
*/
/**
* http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes To find all the prime
* numbers less than or equal to a given integer n by Eratosthenes' method:
* 1. Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
* 2. Initially, let p equal 2, the first prime number.
* 3. Starting from p, count
* up in increments of p and mark each of these numbers greater than p itself
* in the list. These will be multiples of p: 2p, 3p, 4p, etc.; note that
* some of them may have already been marked.
* 4. Find the first number greater than p in
* the list that is not marked. If there was no such number, stop. Otherwise,
* let p now equal this number (which is the next prime), and
* repeat from step 3.
*/
/**
* @author Umang Bhatt
*/
class Node
{
private int no;
private boolean marked;
public Node(int no)
{
this.no = no;
marked = false;
}
public int getNo()
{
return no;
}
public void setNo(int no)
{
this.no = no;
}
public boolean isMarked()
{
return marked;
}
public void setMarked(boolean marked)
{
this.marked = marked;
}
}
public class SieveOfEratosthenes
{
public static void main(String[] args)
{
Scanner aScanner = new Scanner(System.in);
System.out.println("Enter an integer: ");
int no = 0;
try
{
no = aScanner.nextInt();
}
catch (java.util.InputMismatchException e)
{
System.out.println("You entered invalid number. Can not eontinue");
System.exit(0);
}
LinkedList<Integer> primeNumberList = getAllPrimesLessThan(no);
System.out.println("");
for (Integer primeNo : primeNumberList)
{
System.out.print(primeNo + " ");
}
}
/**
* takes a number and returns all the primes.
* @param no is the maximum no. the primes will be below this number.
* @return linked list of integers having only prime numbers
*/
public static LinkedList<Integer> getAllPrimesLessThan(int no)
{
LinkedList<Integer> primeNumberList = new LinkedList<Integer>();
LinkedList<Node> allNUmberList = getNodeListWithItemsLessThan(no);
primeNumberList.addAll(getThefirstUnmarkedAndMarkOtherMultiplesIn(allNUmberList));
primeNumberList.addAll(getUnMarkedIntegers(allNUmberList));
return primeNumberList;
}
/**
* This method created a list of nodes with values between 2 and given number no
* @param no is the limit
* @return the list of nodes
*/
private static LinkedList<Node> getNodeListWithItemsLessThan(int no)
{
LinkedList<Node> nodeList = new LinkedList<Node>();
for (int i = 2; i <= no; i++)
{
Node aNode = new Node(i);
nodeList.add(aNode);
}
return nodeList;
}
/**
* This method adds the first node. Adds it to the primeNumber list and then
* marks all multiples of that number as marked true
*
* @param allNUmberList is the list of nodes created initially
* @return the list of integers.
*/
private static LinkedList<Integer> getThefirstUnmarkedAndMarkOtherMultiplesIn(LinkedList<Node> allNUmberList)
{
LinkedList<Integer> primeNumberList = new LinkedList<>();
for (Node aNode : allNUmberList)
{
if (aNode.isMarked() == false && hasUnmarkedNodes(allNUmberList))
{
Node curruntNode = getFirstUnmarked(allNUmberList);
curruntNode.setMarked(true);
primeNumberList.add(curruntNode.getNo());
markMultiples(allNUmberList, curruntNode.getNo());
}
}
return primeNumberList;
}
/**
* returns the first un-marked node in the list.
* @param aNodeList is the list of nodes.
* @return the first un-marked node.
*/
private static Node getFirstUnmarked(LinkedList<Node> aNodeList)
{
Node returnNode = null;
for (Node aNode : aNodeList)
{
if (!aNode.isMarked())
{
returnNode = aNode;
break;
}
}
return returnNode;
}
/**
* checks whether the list has unmarked nodes
* @param aNodeList
* @return boolean stating whether the list has unmarked nodes or not.
*/
private static boolean hasUnmarkedNodes(LinkedList<Node> aNodeList)
{
boolean hasUnmarkedEntries = false;
for (Node aNode : aNodeList)
{
if (!aNode.isMarked())
{
hasUnmarkedEntries = true;
break;
}
}
return hasUnmarkedEntries;
}
/**
* this method marks all the numbers that are multiples of given number in
* the passed list of nodes.
* @param nodeList is the list of nodes constructed originally
* @param number is the number of which's multiples will be marked.
*/
private static void markMultiples(LinkedList<Node> nodeList, int number)
{
for (Node aNode : nodeList)
{
if (aNode.getNo() % number == 0)
{
aNode.setMarked(true);
}
}
}
/**
* returns all the nodes that are un-marked.
* @param allNUmberList
* @return list of un-marked nodes
*/
private static LinkedList<Integer> getUnMarkedIntegers(LinkedList<Node> allNUmberList)
{
LinkedList<Integer> primeNumberList = new LinkedList<>();
for (Node aNode : allNUmberList)
{
if (!aNode.isMarked())
{
primeNumberList.add(aNode.getNo());
}
}
return primeNumberList;
}
}
|
No comments:
Post a Comment