การถาลแบ่งส่วน (Segmented Sieve)
นี่คือโปรแกรม C++ สำหรับการนำการถาลแบ่งส่วนมาใช้สร้างจำนวนเฉพาะในช่วงที่กำหนด การถาลแบ่งส่วนใช้การถาลง่าย (Simple Sieve) หาจำนวนเฉพาะที่น้อยกว่าหรือเท่ากับ √n ก่อน แนวคิดของอัลกอริทึมนี้คือการแบ่งช่วง [0 ... n-1] ออกเป็นส่วนๆ ต่างๆ และคำนวณจำนวนเฉพาะในแต่ละส่วนทีละส่วน
อัลกอริทึม
เริ่มต้น สร้างฟังก์ชันหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าขีดจำกัด (limit) โดยใช้การถาลเอราโทสเตนีสแบบง่าย หาจำนวนเฉพาะทั้งหมดในช่วงที่กำหนดโดยใช้การถาลแบ่งส่วน A) คำนวณจำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับรากที่สองของ high โดยใช้การถาลง่าย B) นับจำนวนสมาชิกในช่วงที่กำหนด C) ประกาศ boolean เฉพาะสำหรับ [low, high] D) หาตัวเลขขั้นต่ำใน [low ... high] ที่เป็นพหุคูณของ prime[i] (หารด้วย prime[i] ลงตัว) E) ทำเครื่องหมายพหุคูณของ prime[i] ใน [low ... high] F) ตัวเลขที่ไม่ถูกทำเครื่องหมายในช่วง คือจำนวนเฉพาะ สิ้นสุด
โค้ดตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void simpleSieve(int lmt, vector<int>& prime) {
bool mark[lmt + 1];
memset(mark, false, sizeof(mark));
for (int i = 2; i <= lmt; ++i) {
if (mark[i] == false) {
prime.push_back(i);
for (int j = i; j <= lmt; j += i)
mark[j] = true;
}
}
}
void PrimeInRange(int low, int high) {
int lmt = floor(sqrt(high)) + 1;
vector<int> prime;
simpleSieve(lmt, prime);
int n = high - low + 1;
bool mark[n + 1];
memset(mark, false, sizeof(mark));
for (int i = 0; i < prime.size(); i++) {
int lowLim = floor(low / prime[i]) * prime[i];
if (lowLim < low)
lowLim += prime[i];
for (int j = lowLim; j <= high; j += prime[i])
mark[j - low] = true;
}
for (int i = low; i <= high; i++)
if (!mark[i - low])
cout << i << " ";
}
int main() {
int low = 10, high = 50;
PrimeInRange(low, high);
return 0;
}
ผลลัพธ์ตัวอย่าง
11 13 17 19 23 29 31 37 41 43 47
