Liệt kê số chính phương nhỏ hơn N trong C/C++

Liệt kê các số chính phương nhỏ hơn (hoặc bằng) một số nguyên N bất kì, đếm số lượng, tính tổng trong C C++. Cách làm này có thể phù hợp với số nguyên lớn.

1. Giới thiệu bài toán

Khi mới bắt đầu học lập trình, ta thường gặp phải những bài toán ở dạng cơ bản liên quan đến số chính phương, có thể liệt kê một số dạng bài thường gặp như:

1. Liệt kê các số chính phương nhỏ hơn số nguyên n nhập vào từ bàn phím.
2. Liệt kê n số chính phương đầu tiên
3. Liệt kê các số chính phương nhỏ hơn 1000
4. Tính tổng các số chính phương . . .
5. Đếm số lượng số chính phương nhỏ hơn n

Mình đã dành riêng một bài viết về Số chính phương trong C/C++, bạn có thể tham khảo nhé!

Đây là những dạng bài khá hữu ích cho việc học lập trình của bạn, nó giúp bạn vận dụng tốt các kiến thức căn bản. Nói chung chúng rất đơn giản và dễ hiểu. Cùng xem cách giải quyết của mình nhé!

Trong bài viết này mình sẽ giải quyết bài toán đầu tiên nhé, các bài toán 2, 3, 4, 5 cơ bản là tương tự!

2. Ý tưởng giải quyết bài toán

Thông thường các bạn sẽ dùng vòng lặp for từ 0<n sau đó kiểm tra từng số, nếu nó là số chính phương thì in ra màn hình ( tăng biến đếm, cộng tổng . . . ). Tuy nhiên cách làm này không thực sự tối ưu về mặt thời gian. Ta phải tiến hành kiểm tra nhiều lần. Nếu N là một số nguyên lớn (khoảng 10^15) thì tốc độ sẽ rất lâu.

Có thể bạn chưa biết, số lượng số chính phương nhỏ hơn N sẽ là:

• sqrt(N) nếu N không phải là số chính phương
  sqrt(N) – 1 nếu N là một số chính phương

Dựa vào tính chất trên mình sẽ kiểm tra xem N có phải SCP không. Sau đó mình sẽ khai báo một biến a có giá trị là a = sqrt(N).
Nếu N là SCP: for( int i =1; i<a;i++) , in ra màn hình i*i
Ngược lại: for( int i =1; i<=a;i++) , in ra màn hình i*i
(i*i chính là các SCP nhỏ hơn N)

3. Code in ra màn hình số chính phương nhỏ hơn N

Với tư tưởng mình đã nêu ở phần trên của bài viết, trong phần này mình sẽ show code luôn nhé!

/* Code by duongdinh24.com
   Github: https://github.com/duongdinh24/
*/
#include<iostream>
#include<math.h>   // thư viện toán học để dùng hàm sqrt
using namespace std;

// Ham kiem tra so chinh phuong
bool checkSquareNumber(int n){
	if(n<1)
		return false;
	int i = sqrt(n);
	if(i*i==n)
		return true;
	return false;
}

// Ham liet ke so chinh phuong nho hon n
void printSquareNumber(int n){
	cout<<"Cac so chinh phuong nho hon "<<n<<endl;
	int a = sqrt(n);
	if(checkSquareNumber(n))
		for(int i=1;i<a;i++)
			cout<<i*i<<" ";
	else
		for(int i=1;i<=a;i++)
			cout<<i*i<<" ";
}
int main(){
	int n;
	// Nhap n tu ban phim
	do{
		cout<<"Nhap n: ";
		cin>>n;
	}
	while(n<=0);

	printSquareNumber(n);
	return 0;
}

Ví dụ đầu tiên nhập n = 36. Các số cp nhỏ hơn 36 sẽ là 1, 4, 9, 16, 25

Ví dụ 2: n=37 ta sẽ thu được kết quả như hình:

Lời kết:

Bài viết của mình đến đây là hết, nếu bạn có bất kì thắc mắc hay ý kiến đóng góp hãy để lại comment xuống phía dưới nhé!
Xem thêm các bài viết về C/C++ của mình tại đây.
Cảm ơn bạn đã ghé thăm duongdinh24.com! Chúc bạn học tập thành công!