Phương pháp Sàng bánh xe (Wheel Sieve) được dùng để tìm số nguyên tố trong một khoảng cho trước. Phân tích nhân tử bánh xe (Wheel factorization) là một phương pháp đồ họa để thực hiện thủ công một bước sơ bộ cho Sàng Eratosthenes, phân tách số nguyên tố khỏi hợp số.
Trong phương pháp này, các số nguyên tố trong vòng tròn bên trong có các bội số ở các vị trí tương tự như chính chúng ở các vòng tròn khác, tạo ra các chông chênh của số nguyên tố và bội số của chúng. Bội số của các số nguyên tố này trong vòng tròn bên trong tạo thành các chông chênh của hợp số ở các vòng tròn bên ngoài.
Thuật toán
Bắt đầu
Định nghĩa số tối đa
gen_sieve_primes()
Khai báo c
Gán c = 2
For p = 2 đến max number
If prime[p] == 0
prime[p] = 1
Mul = p nhân c
For Mul nhỏ hơn max number
prime[Mul] = -1
Tăng c
Mul = p nhân c
Print_all_prime()
Gán c = 0
For i = 0 đến max number
if (prime[i] == 1)
Tăng c
If c nhỏ hơn 4
Switch(c)
Case 1: In số nguyên tố thứ 1
Case 2: In số nguyên tố thứ 2
Case 3: In số nguyên tố thứ 3
Else
In số nguyên tố thứ n
Kết thúc
Mã ví dụ
#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;
}
Kết quả đầu ra
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