The Sieve of Eratosthenes is a mechanism forfinding prime numbers (an integer la

Question

The Sieve of Eratosthenes is a mechanism forfinding prime numbers (an integer larger than 1 which is divisibleonly by itself and 1).

The Sieve of Eratosthenes will be describedhere as a "pen and paper" exercise. Your task is to implement thisas a Java program. Use your own discretion in making reasonabledecisions about how to implement aspects of the program that arenot specified here.

Algorithm:

Write down all integers from 2 to the largest integer ofinterest. The approach is to then cross out integers that have beenshown to be composite (i.e., not prime). This is achieved simply asfollows:

For each integer in the list
If the integer has been crossed out
Return to the start of the loop with the next integer
Cross out all multiples of the integer in the list
Return to the start of the loop

For each integer in the list
If the integer has not been crossed out then announce it asprime

Example:
To find all primes up to 20, write down integers 2 to20:

Now start at '2'. Cross out all of its multiples:

Trace this problem on paper to ensure that you understand theprocess. Then consider the design issues prior to coding.

Now write a Java program that willread a number N and will then use Eratosthenes Sieve to determinethe prime numbers up to (and including) N and print them one perline, don't print any extra information. The Java program must bein a class called Task.

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Explanation / Answer

please rate - thanks import java.util.*; public class Task {public static void main(String[] args) {int i,j,max; Scanner in=new Scanner(System.in); System.out.println("Enter number: "); max=in.nextInt(); boolean sieve[]=new boolean[max]; for(i=0;i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.