Place your code \"Homework4Problem1. java\" and \"HomeworkAProblem2.java\" on bl
ID: 3825664 • Letter: P
Question
Place your code "Homework4Problem1. java" and "HomeworkAProblem2.java" on blackboared by the date given. Create a program that generates a file of all the prime numbers less than a number N taken from command line. It is up to you how you store this data into the file as long as your next problem can read it. Your program should work for numbers up to 100,000. You must implement the Sieve of Eratosthenes in order to generate this file. You are welcome to take a look at the wikipedia source on this which even includes some pseudocode https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Example input: 10 Example output in "file.txt": 2 3 5 7 Create a program that takes a file of prime numbers generated from Problem 1 and stores them in any way of your choosing. The user may query the program as many times as they would like and it will output whether or not the number given is prime. The queries must run in log(n) time where n is the amount of prime numbers in the file. If the number that is entered is negative stop the program. If the number is greater than the largest in the file inform the user that they need a file which contains more prime numbers. Example input in "file.txt"; 2 3 5 7 Example command line interaction with user: Enter a number 3 3 is a prime number. Enter another number. 4 4 is not a prime number. Enter another number. 8 Current file not large enough for 8. Enter another number. -1Explanation / Answer
package chegg.datastructure;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class SieveOfEratosthenesAlgorithum {
public static void sieveOfEratosthenes() {
Scanner scanner = null;
try {
scanner = new Scanner(System.in);
System.out
.println("Enter the max number limit for which you need to process the prime number ");
int maxPrimeNum = scanner.nextInt();
boolean prime[] = new boolean[maxPrimeNum + 1];
for (int i = 0; i < maxPrimeNum; i++)
prime[i] = true;
for (int p = 2; p * p <= maxPrimeNum; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= maxPrimeNum; i += p)
prime[i] = false;
}
}
// Print all prime numbers
StringBuilder string = new StringBuilder("");
for (int i = 2; i <= maxPrimeNum; i++) {
if (prime[i] == true)
string.append(i + ",");
}
SieveOfEratosthenesAlgorithum.writeFile(new File("d:\deepak.txt"),
string.substring(0, string.length() - 1));
String commaSperatedNumber = SieveOfEratosthenesAlgorithum
.readFile(new File("d:\deepak.txt"));
String[] inputArray = commaSperatedNumber.split(",");
System.out
.println("Enter the prime number which you want to search from file ");
int numberToBeSearched = scanner.nextInt();
if (numberToBeSearched < 0) {
System.out
.println("Entered number is less the zero. oops program is going to be terminated.");
return;
} else if (Integer.parseInt(inputArray[(inputArray.length - 1)]) < numberToBeSearched) {
System.out
.println("need a file which containning more larger prime number.");
return;
} else {
int result = SieveOfEratosthenesAlgorithum.binarySearch(
inputArray, numberToBeSearched);
if (result == -1) {
System.out.println(" prime number not found in a file");
} else {
System.out.println(" prime number Found");
}
}
} catch (Exception e) {
System.out.println(e.getMessage());
e.printStackTrace();
} finally {
if (scanner != null) {
scanner.close();
}
}
}
/**
*
*/
private static void writeFile(File fileName, String content) {
System.out.println(content + "/" + fileName);
if (content == null || content.length() < 0)
return;
try (FileWriter fw = new FileWriter(fileName, false);
BufferedWriter bw = new BufferedWriter(fw);
PrintWriter out = new PrintWriter(bw)) {
out.println(content);
} catch (IOException e) {
e.printStackTrace();
}
}
/**
*
* @param fileNameWithPath
* @return
*/
public static String readFile(File fileNameWithPath) {
List<String> list = new ArrayList<String>();
try (BufferedReader br = new BufferedReader(new FileReader(
fileNameWithPath))) {
String sCurrentLine;
while ((sCurrentLine = br.readLine()) != null) {
list.add(sCurrentLine);
}
} catch (IOException e) {
e.printStackTrace();
}
return list.get(0);
}
public static int binarySearch(String[] inputArr, int key) {
int start = 0;
int end = inputArr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (key == Integer.parseInt(inputArr[mid])) {
return mid;
}
if (key < Integer.parseInt(inputArr[mid])) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
// Driver Program to test above function
public static void main(String args[]) {
System.out
.print("Following are the prime numbers smaller than or equal to ");
SieveOfEratosthenesAlgorithum.sieveOfEratosthenes();
}
}
Description
-----------------
1. Program will write prime numbers in comma spearted form and read all teh number is single string with sorted number.
2. I have used binary search ( divided and conquer technique ) whihc takes o log(n) time complacxity where n is prime numbers, array containning.
3. i have writeFile and readfile method in above code which is responsible for writting and reading file form d drive of your system. You can chnage the name and directory . Please check the main method.
Please le me know if you face any challanges to understand the above code,
Output
-----------------
Following are the prime numbers smaller than or equal to
Enter the max number limit for which you need to process the prime number
1000
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997/d:deepak.txt
Enter the prime number which you want to search from file
101
prime number Found