//Java Homework Permit the user to enter a value for n, and then use the followi
ID: 3744829 • Letter: #
Question
//Java Homework
Permit the user to enter a value for n, and then use the following algorithm to display the prime numbers in the range 2 to n.
Start with a table of numbers (e.g., 2, 3, 4, 5, . . ., n) and progressively cross off numbers in the table until the only numbers left are primes.
Specifically, we begin with the first number, p, in the table, and
1. Declare p to be prime, then display it
2. Cross off all the multiples of that number in the table, starting from p2
3. Find the next number in the table after p that is not yet crossed off, and set p to that number
4. Repeat steps 1 to 3 until you check n.
The starting point of p2 is a pleasing but minor optimization, which can be made because lower multiples will have already been crossed off when we found the primes prior to p.
For a fixed size table of size n, once we have reached the p2 entry in the table, we need perform no more crossings off— we can simply read the remaining table entries and know them all to be prime.
Therefore, we can adjust the above algorithm as follows:
Specifically, we begin with 2, the first number in the table, and
1. If this number, p, has not been crossed off, it is prime, display it.
2. Cross off all the multiples of p in the table, starting from p2. As stated in the last sentence of the previous paragraph, this is only necessary if .
3. Repeat steps 1 to 2 until p > n, where p is the next number in the table.
// You must follow the outline code below.
Explanation / Answer
import java.util.*;
import java.util.Scanner;
public class SieveOfEratosthenes {
public static void main(String args[]) {
//Scanner Object used to get user input from console
Scanner scanner = new Scanner(System.in);
//Prompt User to enter a number
System.out.print("Enter a number:");
int n = scanner.nextInt();
scanner.close();
//Create table of numbers according to n that user specified
int [] table = new int[n];
//Array name followed by .length will give us size of array, in this case it will be n
int arraySize = table.length;
int idx = 0;
int num = 1;
//Fill table with numbers
while(idx < arraySize) {
table[idx] = num;
idx++;
num++;}
//square root method will not work for 2,and 3 so hard code it
System.out.println(3+" Is prime");
for(int i= 4;i<arraySize;i++){
//Intialize flag to true
boolean flag=true;
//Check untill square root of number
//If number is not-prime then its factor is present in that range(2 to Math.sqrt(number))
for(int j=2;j<=(int)Math.sqrt(i);j++){
if(i%j==0){
//If factor is found make flag false
flag=false;
//If factor present then break out of loop
break;
}
}
//If flag ids true that means No factor is found hence it is Prime
//Hence print the result
if(flag)
System.out.println(i+" Is prime");
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.