SPOJ.COM - Thuật toán bài TDPRIMES - Printing some primes

Đề bài:

Yêu cầu của bài toán vô cùng đơn giản. Hãy in ra tất cả số nguyên tố nhỏ hơn 10^8.

Đầu vào

Không có đầu vào

Đầu ra

Để giúp cho bài toán có ít kết quả hơn, hãy in ra tất cả số nguyên tố thứ 1, 101, 201,...(những số chia cho 100 thì dư 1).

Ví dụ

Đầu vào:

Đầu ra:

2 
547 
1229 
... 
99995257 
99996931 
99998953

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/TDPRIMES/

Phân tích

Bài này mình xếp vào loại sử dụng thuật toán tham lam Greedy

Ở đây, nếu suy nghĩ theo cách thông thường, chắc hẳn bạn sẽ viết một hàm kiểm tra xem 1 số có phải số nguyên tố hay không. Sau đó, duyệt từ 1 cho đến 10^8 để kiểm tra từng số xem nó có phải số nguyên tố hay không. Rồi in ra những số nguyên tố thứ 1, 101, 201,... Tuy nhiên, nếu làm theo cách này chắc chắn bạn sẽ bị time limit.

Đối với bài toán này, mình sử dụng phương pháp sàng Eratosthenes để tìm ra các số nguyên tố.

Để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên N bằng sàng Eratosthenes, ta làm như sau:

• Bước 1: Tạo 1 danh sách các số tự nhiên liên tiếp từ 2 đến n: (2, 3, 4,..., n).
• Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.
• Bước 3: Tất cả các bội số của p: 2p, 3p, 4p,... sẽ bị đánh dấu vì không phải là số nguyên tố. -
• Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p. Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include<stdio.h>
using namespace std;

const int MAX = 100000000;
bool prime[MAX];// Đánh dấu xem số i có phải là số nguyên tố không

int main()
{
	for(int i = 2; i < MAX; i++)
		prime[i] = true;

	// Số nguyên tố đầu tiên là số 2
	printf("2\n");

	int cnt_prime = 1;	// Đếm số nguyên tố

	// Dùng phương pháp sàng để đánh dấu các số nguyên tố.
	// Số chẵn lớn hơn 2 chắc chắn không phải là số nguyên tố.
	// Nên ta chỉ cần kiểm tra số lẻ.
	// Nguyên tắc: nếu số i là số nguyên tố => 3*i, 5*i, 7*i,...
	// không phải số nguyên tố
	int i;
	for(i = 3; i*i < MAX; i=i+2)
		if(prime[i])
		{
			cnt_prime++;
			if(cnt_prime % 100 == 1) printf("%d\n",i);

			int j = 3;
			while(i*j < MAX)
			{
				prime[i*j] = false;
				j += 2;
			}
		}

	// In ra số nguyên tố còn lại
	for(int j = i; j < MAX; j+=2)
		if(prime[j])
		{
			cnt_prime++;
			if(cnt_prime % 100 == 1) printf("%d\n",j);
		}

	return 0;
}