ในบทความนี้ เราจะอธิบายวิธีการหาจำนวนเฉพาะในอาร์เรย์ย่อย เรามีอาร์เรย์ของจำนวนบวก arr[] และ q แบบสอบถามที่มีจำนวนเต็มที่สองตัวที่แสดงถึงช่วงของเรา {l, R} เราจำเป็นต้องค้นหาจำนวนเฉพาะในช่วงที่กำหนด ด้านล่างนี้เป็นตัวอย่างของปัญหาที่กำหนด -
Input : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3
Output : 2
In the given range the primes are {2, 3}.
Input : arr[] = {2, 3, 5, 8 ,12, 11}, q = 1, L = 0, R = 5
Output : 4
In the given range the primes are {2, 3, 5, 11}. แนวทางในการหาแนวทางแก้ไข
ในสถานการณ์นี้ มีสองวิธีอยู่ในใจ -
กำลังดุร้าย
ในแนวทางนี้ เราสามารถหาช่วงและหาจำนวนเฉพาะที่มีอยู่ในช่วงนั้นได้
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int N){
if (N <= 1)
return false;
if (N <= 3)
return true;
if(N % 2 == 0 || N % 3 == 0)
return false;
for (int i = 5; i * i <= N; i = i + 2){ // as even number can't be prime so we increment i by 2.
if (N % i == 0)
return false; // if N is divisible by any number then it is not prime.
}
return true;
}
int main(){
int N = 6; // size of array.
int arr[N] = {1, 2, 3, 4, 5, 6};
int Q = 1;
while(Q--){
int L = 0, R = 3;
int cnt = 0;
for(int i = L; i <= R; i++){
if(isPrime(arr[i]))
cnt++; // counter variable.
}
cout << cnt << "\n";
}
return 0;
} ผลลัพธ์
2
อย่างไรก็ตาม แนวทางนี้ไม่ค่อยดีนักเนื่องจากความซับซ้อนโดยรวมของแนวทางนี้คือ O(Q*N*√N) ซึ่งไม่ค่อยดีนัก
แนวทางที่มีประสิทธิภาพ
ในแนวทางนี้ เราจะใช้ Sieve Of Eratosthenes เพื่อสร้างอาร์เรย์บูลีนที่บอกเราว่าองค์ประกอบนั้นเป็นจำนวนเฉพาะหรือไม่ จากนั้นจึงผ่านช่วงที่กำหนดและหาจำนวนเฉพาะของจำนวนเฉพาะจากอาร์เรย์บูล
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX){
vector<bool> p(n);
bool Prime[MAX + 1];
for(int i = 2; i < MAX; i++)
Prime[i] = true;
Prime[1] = false;
for (int p = 2; p * p <= MAX; 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 <= MAX; i += p)
Prime[i] = false;
}
}
for(int i = 0; i < n; i++){
if(Prime[arr[i]])
p[i] = true;
else
p[i] = false;
}
return p;
}
int main(){
int n = 6;
int arr[n] = {1, 2, 3, 4, 5, 6};
int MAX = -1;
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]);
}
vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX); // boolean array.
int q = 1;
while(q--){
int L = 0, R = 3;
int cnt = 0; // count
for(int i = L; i <= R; i++){
if(isprime[i])
cnt++;
}
cout << cnt << "\n";
}
return 0;
} ผลลัพธ์
2
คำอธิบายของโค้ดด้านบน
วิธีการนี้เร็วกว่าแนวทาง Brute Force ที่เรานำมาใช้ก่อนหน้านี้มาก เนื่องจากตอนนี้ความซับซ้อนของเวลาคือ O(Q*N) ซึ่งดีกว่าความซับซ้อนก่อนหน้านี้มาก
ในแนวทางนี้ เราคำนวณองค์ประกอบล่วงหน้าและตั้งค่าสถานะเป็นจำนวนเฉพาะหรือไม่ ดังนั้นจึงลดความซับซ้อนของเราลง ยิ่งไปกว่านั้น เรายังใช้ Sieve Of Eratosthenes ซึ่งช่วยให้เราค้นหาจำนวนเฉพาะได้เร็วขึ้น ในวิธีนี้ เราตั้งค่าสถานะตัวเลขทั้งหมดเป็นจำนวนเฉพาะหรือไม่เฉพาะใน O(N*log(log(N))) ความซับซ้อนโดยการตั้งค่าสถานะตัวเลขโดยใช้ตัวประกอบเฉพาะ
บทสรุป
ในบทความนี้ เราแก้ปัญหาเพื่อค้นหาจำนวนเฉพาะใน Subarray ใน O(Q*N) โดยใช้ Sieve Of Eratosthenes นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติและมีประสิทธิภาพ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ
