TDPRIMES.cpp

#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;
}