การถาลล้อ (Wheel Sieve)
วิธีการถาลล้อใช้หาจำนวนเฉพาะในช่วงที่กำหนด การแยกตัวประกอบล้อ (Wheel factorization) เป็นวิธีทางกราฟิกสำหรับการทำขั้นตอนเตรียมการแบบมืออาชีพสำหรับการถาลเอราโทสเตนีส ที่แยกจำนวนเฉพาะออกจากตัวเลขประกอบ (composites)
ในวิธีนี้ จำนวนเฉพาะในวงในสุดจะมีพหุคูณในตำแหน่งที่คล้ายกันเหมือนตัวมันเองในวงอื่นๆ ทำให้เกิดเส้นลวดล้อ (spokes) ของจำนวนเฉพาะและพหุคูณของมัน พหุคูณของจำนวนเฉพาะเหล่านี้ในวงในสุดจะสร้างเส้นลวดล้อของตัวเลขประกอบในวงนอก
อัลกอริทึม
เริ่มต้น
กำหนดหมายเลขสูงสุด (max number)
gen_sieve_primes()
ประกาศ c
กำหนด c = 2
For p = 2 ถึง max number
If prime[p] == 0
prime[p] = 1
Mul = p คูณ c
For Mul น้อยกว่า max number
prime[Mul] = -1
เพิ่ม c
Mul = p คูณ c
Print_all_prime()
กำหนด c = 0
For i = 0 ถึง max number
if (prime[i] == 1)
เพิ่ม c
If c น้อยกว่า 4
Switch(c)
Case 1: พิมพ์จำนวนเฉพาะลำดับที่ 1
Case 2: พิมพ์จำนวนเฉพาะลำดับที่ 2
Case 3: พิมพ์จำนวนเฉพาะลำดับที่ 3
Else
พิมพ์จำนวนเฉพาะลำดับที่ n
สิ้นสุด
โค้ดตัวอย่าง
#include <iostream>
using namespace std;
#define MAX_NUMBER 40
int prime[MAX_NUMBER];
void gen_sieve_prime(void) {
for (int p = 2; p < MAX_NUMBER; p++) {
if (prime[p] == 0)
prime[p] = 1;
int c = 2;
int mul = p * c;
for (; mul < MAX_NUMBER;) {
prime[mul] = -1;
c++;
mul = p * c;
}
}
}
void print_all_prime() {
int c = 0;
for (int i = 0; i < MAX_NUMBER; i++) {
if (prime[i] == 1) {
c++;
if (c < 4) {
switch (c) {
case 1:
cout << c << "st prime is: " << i << endl;
break;
case 2:
cout << c << "nd prime is: " << i << endl;
break;
case 3:
cout << c << "rd prime is: " << i << endl;
break;
default:
break;
}
} else
cout << c << "th prime is: " << i << endl;
}
}
}
int main() {
gen_sieve_prime();
print_all_prime();
return 0;
}
ผลลัพธ์ตัวอย่าง
1st prime is: 2 2nd prime is: 3 3rd prime is: 5 4th prime is: 7 5th prime is: 11 6th prime is: 13 7th prime is: 17 8th prime is: 19 9th prime is: 23 10th prime is: 29 11th prime is: 31 12th prime is: 37
