資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Java程式實現輪篩法生成指定範圍內的素數
尋找給定範圍內的素數的簡單方法是檢查每個數是否為素數。此外，我們需要進行等於給定數字的迭代以檢查該數字是否為素數。因此，簡單方法非常耗時，我們需要對其進行最佳化以提高效率。
在本教程中，我們將學習由Sieve給出的輪因子分解和埃拉託斯特尼篩法演算法，以有效地找到給定範圍內的素數。
問題陳述 - 我們給出了左整數和右整數的值。我們需要實現輪因子分解和埃拉託斯特尼篩法演算法來找到給定範圍內的素數。
示例
輸入
left = 10; right = 50;
輸出
11 13 17 19 23 29 31 37 41 43 47
解釋
It prints the prime numbers between 10 and 50.
輸入
left = 9; right = 10;
輸出
“”
解釋
It prints an empty string as there is no prime numbers between 9 and 10.
輸入
left = 144; right = 200;
輸出
149 151 157 163 167 173 179 181 191 193 197 199
方法1
在這種方法中，我們將使用埃拉託斯特尼篩法演算法來查詢兩個給定數字之間的素數。
在埃拉託斯特尼篩法演算法中，我們使用長度為N的陣列來根據數字是否為素數來儲存布林值。我們將偶數儲存為false，因為它們是非素數。之後，我們訪問每個未標記的數字，並將它的倍數的布林值從true更改為false。
演算法
步驟1 - 定義numbers[]陣列以根據數字是否為素數儲存布林值。
步驟2 - 執行createMatrix()函式以查詢1到10,000,000之間的素數並更新numbers[]陣列。
步驟3 - 從4開始遍歷到給定範圍。如果索引為偶數，則將numbers[p]初始化為false。否則為true。
步驟4 - 使用迴圈從3迭代到給定範圍。如果number[p]為true，則將該數字的所有倍數標記為false。
步驟5 - 執行getPrimes()函式以獲取左值和右值之間的所有素數。
步驟5.1 - 在getPrimes()函式中，遍歷給定範圍內的陣列，如果陣列元素為true，則列印索引值。
示例
import java.io.*;
public class Main {
// Maximum range
static boolean numbers[] = new boolean[1000001];
static void createMatrix() {
// max range
int range = 1000000;
// Initially mark even numbers as non-prime and odd numbers as prime
for (int p = 4; p <= range; ++p) {
if (p % 2 == 0)
numbers[p] = false;
else
numbers[p] = true;
}
// Traverse all odd numbers and update if the number is not prime
for (int p = 3; p <= Math.sqrt(range); p += 2) {
// If the number is prime
if (numbers[p] == true) {
// Update all multiples of p as non-prime
for (int q = p * p; q <= range; q += p) {
numbers[q] = false;
}
}
}
}
static void getPrimes (int left, int right) {
System.out.println("Prime numbers in the given range are:");
for (int p = left; p <= right; ++p) {
// Printing prime numbers in the range
if (numbers[p] == true) {
System.out.print(p + " ");
}
}
}
public static void main(String[] args) {
int left = 10;
int right = 50;
createMatrix();
// Get prime numbers in the given range
getPrimes(left, right);
}
}
輸出
Prime numbers in the given range are: 11 13 15 17 19 21 23 27 29 31 33 37 39 41 43 47
時間複雜度 – O(N*logN)，其中O(N)用於遍歷陣列，O(logN)用於將所有倍數標記為false。
方法2
在這種方法中，我們需要獲取素數的基本列表。這裡，我們將使用{2, 3, 5}。之後，我們需要在將基本列表的所有素數相乘後決定輪的大小。因此，我們的輪大小將為(2*3*5)30。
在下一步中，我們需要獲取1到輪大小的所有素數以構成一個輪。我們將採用{7, 11, 13, 17, 19, 23, 29, 31}，因為我們已經在基本列表中包含了2, 3和5。
因此，輪包含一層30個數。在每一層中，我們檢查數字是否可以被任何最小整數整除以確保該數字是否為素數。
演算法
步驟1 - 將'isNumPrime'初始化為true，假設該數字為素數。
步驟2 - 同樣，將primes陣列初始化為輪的第一層的素數。
步驟3 - 如果數字小於2，則將'isNumPrime'更新為false。
步驟4 - 如果數字可以被2、3或5整除，則將'isNumPrime'更新為false。
步驟5 - 使用迴圈從0到sqrt(Number)以30為步長進行迭代，因為輪的每一層包含30個數。
步驟6 - 使用巢狀迴圈遍歷第一層的所有素數。如果第一層的素數大於sqrt(num)，則中斷巢狀迴圈。
步驟7 - 否則，如果數字可以被第一層的素數 + p（30的倍數）整除，則將'isNumPrime'更新為false並中斷巢狀迴圈。
步驟8 - 在外迴圈中，如果'isNumPrime'的值為false，則中斷外迴圈。
步驟9 - 返回'isNumPrime'變數的值。
示例
在這個例子中，我們遍歷給定範圍內的每個數字，並使用輪因子分解演算法檢查它是否為素數。
import java.util.*;
public class Main {
static boolean checkForPrime(int num) {
boolean isNumPrime = true;
// Wheel of prime numbers
int[] primes = { 7, 11, 13, 17, 19, 23, 29, 31 };
// Base Case
if (num < 2) {
isNumPrime = false;
}
if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0) {
isNumPrime = false;
}
// Check in the wheel P is the layer of the wheel
for (int p = 0; p < Math.sqrt(num); p += 30) {
// Check for the list of Sieve in primes[]
for (int pm : primes) {
// When the prime number exceeds the square root of the num
if (pm > Math.sqrt(num)) {
break;
}
// If num is multiple of pm in the current wheel
else {
if (num % (pm + p) == 0) {
isNumPrime = false;
break;
}
}
// When a number is non-prime in the current layer
if (!isNumPrime)
break;
}
}
return isNumPrime;
}
public static void main(String args[]) {
int left = 10;
int right = 50;
System.out.println("Prime numbers in the given range are :");
for (int p = left; p <= right; ++p) {
if (checkForPrime(p) == true) {
System.out.print(p + " ");
}
}
}
}
輸出
Prime numbers in the given range are: 11 13 17 19 23 29 31 37 41 43 47
時間複雜度 – O(N*N1/2)
空間複雜度 – O(1)
只有當我們需要在一個特定範圍內查詢素數時才使用埃拉託斯特尼篩法演算法，而輪因子分解演算法用於查詢大範圍內的所有素數。
瀏覽量：183
