The Sieve of Eratosthenes is an ancient and efficient algorithm for finding all prime numbers up to a specified limit. It was developed by the ancient Greek mathematician Eratosthenes, around 240 BCE. The algorithm works by iteratively marking multiples of each prime number as composite until no more prime numbers can be found. Here's a step-by-step explanation of the Sieve of Eratosthenes algorithm:
1. Create a boolean array: Create a boolean array `prime[0..n]` and initialize all entries as `true`. The boolean array will be used to mark numbers as prime or composite.
2. Initialize variables : Set `p` to 2, as 2 is the first prime number.
3. Mark composites: Starting from `p`, the first prime number, iterate through the array and mark all multiples of `p` (excluding `p` itself) as composite by setting their corresponding values in the boolean array to `false`. These multiples will be `2 * p`, `3 * p`, `4 * p`, and so on, up to `n`.
4. Find the next prime: Search for the next available (not marked as composite) number greater than `p` in the array. This will be the next prime number.
5. Repeat: Set `p` to the next prime found in the previous step and go back to step 3. Continue this process until `p` squared is greater than `n`. At this point, all the remaining numbers in the boolean array that are still marked as `true` are prime numbers.
6. Collect prime numbers : Create a list to store the prime numbers and add all the remaining numbers from the boolean array (indices marked as `true`) to the list.
Program in Java :
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the Upper Bound : ");
int n = sc.nextInt();
boolean[] array = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
array[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (array[i]) {
for (int j = i * i; j <= n; j += i) {
array[j] = false;
}
}
}
System.out.println("Prime numbers from 2 to " + n + " :");
for (int i = 2; i <= n; i++) {
if (array[i]) {
System.out.print(i + " ");
}
}
}
}
Explanation :
1. Import Statement:
import java.util.*;
This line imports the `java.util` package, which includes the `Scanner` class that we use to read input from the user.
2. Class Declaration:
public class Main {
Here, we define a public class named `Main`.
3. Main Method:
public static void main(String[] args) {
The `main` method is the entry point of the program. It's where the program starts execution.
4. Input Handling:
Scanner sc = new Scanner(System.in);
System.out.println("Enter the Upper Bound");
int n = sc.nextInt();
The code above creates a `Scanner` object (`sc`) to read input from the user. It then prompts the user to enter an upper bound (a positive integer) and reads the input into the variable `n`.
5. Array Initialization:
boolean[] array = new boolean[n + 1];
An array `array` of boolean values is created with a size of `n + 1`. This array will be used to store information about prime numbers.
6. Sieve of Eratosthenes Algorithm:
for (int i = 2; i <= n; i++) {
array[i] = true;
}
This loop initializes all elements of the `array` to `true` except for the first two elements (index 0 and 1), as 0 and 1 are not prime numbers.
for (int i = 2; i * i <= n; i++) {
if (array[i]) {
for (int j = i * i; j <= n; j += i) {
array[j] = false;
}
}
}
This loop implements the Sieve of Eratosthenes algorithm to mark non-prime numbers as `false`. The algorithm works by starting with the first prime number (2) and marking all of its multiples as non-prime. Then it moves on to the next unmarked number (which is a prime) and repeats the process until all numbers are processed up to the square root of `n`.
7. Output Prime Numbers:
System.out.println("Prime numbers from 2 to " + n + ":");
for (int i = 2; i <= n; i++) {
if (array[i]) {
System.out.print(i + " ");
}
}
Finally, this loop prints the prime numbers by checking the `array` for `true` values. If `array[i]` is `true`, it means that `i` is a prime number, so it is printed.
In summary, this Java program uses the Sieve of Eratosthenes algorithm to find and print all prime numbers from 2 up to the upper bound specified by the user.
No comments:
Post a Comment