Lập trình C++

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.

Published by

tuanitpro

Tôi là Lê Thanh Tuấn, và tôi chia sẻ những điều mình cho rằng nó là thú vị, hay giúp ích cho bạn!

One thought on “Tìm số nguyên tố trong C++”

Leave a Reply