Tìm số nguyên tố trong C++

Tìm số nguyên tố trong C++ là bài tập thú vị mà bất cứ ai khi học C++ cũng có thể gặp qua. Kiểm tra số có phải là số nguyên tố không? Xuất danh sách các số nguyên tố từ 1 đến n. Xuất các số nguyên tố trong mảng. Tính tổng các số các số nguyên tố trong mảng…

Ví dụ dưới đây cho phép bạn kiểm tra 1 số n có phải số nguyên tố hay không?

Ý tưởng: Số nguyên tố là số chỉ chia hết cho 1 và chính nó. Ta sẽ duyệt danh sách từ 2 đến sqrt(n). Nếu n chia hết cho 1 số thứ 3 thì nó không phải là số nguyên tố. Ngược lại n là số nguyên tố.

// Ham kiem tra 1 so co phai la so NT hay khong? Dung thi tra ve 1, nguoc lai tra ve 0
int KiemTraSNT(int n) {	 
	if (n == 2) {
		return 1;
	}
	else {
		for (int i = 2; i <= int(sqrt(n)); i++)
		{
			if (n%i == 0) {
				return 0;				
			}
		}
	}
	return 1;
}

so-nguyen-to

 

Áp dụng tính tổng các số nguyên tố từ 1 đến n

int TinhTongCacSoNT(int n) {
	int tong = 0, x = 0;
	for (int i = 2; i <= n; i++)
	{
		x = KiemTraSNT(i);
		if (x == 1)
			tong += i;
	}
	return tong;
}

Chúc các bạn thành công.