완전제곱수(Perfect Square Number, 제곱수, 정사각수)

완전제곱수(Perfect Square Number, 제곱수, 정사각수)

정사각수(Square Number)

• 어떤 자연수의 제곱이 되는 `1^{2}, 2^{2}, 3^{2}, 4^{2}`과 같은 수를 완전제곱수(Perfect Square Number) 또는 제곱수(Square Number) 또는 정사각수라고 한다.

1 = 1² 1 + 3 = 2² 1 + 3 + 5 = 3² 1 + 3 + 5 + 7 = 4² 1 + 3 + 5 + 7 + 9 = 5²

• 위에서와 같이 1부터 연속된 홀수의 합은 언제나 완전제곱수임을 알 수 있다.

 

완전제곱수 판별하기

① 약수의 개수를 이용한 완전제곱수 판별

• 완전제곱수는 약수의 개수가 언제나 홀수개이므로 약수의 개수를 확인하여 완전제곱수인지 판별할 수 있다.

 

예제

1부터 100까지의 수 중, 완전제곱수 찾기

#include <iostream>
using namespace std;

int main() {
    int cnt;
    
    for (int i = 1; i <= 100; i++) {
        cnt = 0;
        for (int j = 1; j <= i; j++) {    // 각각의 i에 대한 약수의 개수 구하기
            if (i % j == 0) {
                cnt++;
            }
        }
        
        if (cnt % 2 == 1) {    // 약수의 개수가 홀수개이면 완전제곱수
            cout << i << endl;
        }
    }
    
    return 0;
}

1
4
9
16
25
36
49
64
81
100

 

② 제곱근을 이용한 완전제곱수 판별

• 어떤 수가 완전제곱수인지 판별하기 위해서는 어떤 수의 제곱근을 정수 부분만 취한 후 정수 부분을 제곱한 수와 어떤 수가 같으면 완전제곱수임을 판별할 수 있다.
• 예) 4의 제곱근은 2.000 이고, 이 중에서 정수 부분인 2의 제곱 4(= 2 * 2)는 4와 같으므로, 4는 완전제곱수이다.
• C++에서 sqrt() 함수를 이용하여 제곱근을 구한다.
  • Square Root
  • <cmath> 헤더 파일을 불러와야 사용할 수 있다.
  • sqrt(n)은 `\sqrt{n}`과 같다.
  • double 형의 값이 출력된다.

 

예제

1부터 100까지의 수 중, 완전제곱수 찾기

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int k;
    
    for (int i = 1; i <= 100; i++) {
        k = sqrt(i);
        if (k * k == i) {
            cout << i << endl;
        }
    }
    
    return 0;
}

1
4
9
16
25
36
49
64
81
100

 

③ 순환문을 이용한 완전제곱수 판별

• 다음과 같이 순환문을 이용하여 완전제곱수를 판단할 수 있다.

for (int k = 1; k * k < i; k++);
if (k * k == i) {
    cout << i << endl;
}

• 어떤 수 i가 제곱수인지 판별하기 위해서 k의 값은 1부터 순환을 시작한다. for 문의 기능은 단지 순환의 역할만 할 뿐 for 문 안의 내용은 아무것도 없다.
• for 문의 순환은 k * k의 값이 i의 값보다 작다면 k의 값으 계속 1씩 증가하며 순환한다.
• for 문의 순환이 완료되었을 때는 k * k의 값이 i의 값과 같거나 또는 i의 값보다 클 때이다.
• 만약 k * k 의 값이 i의 값과 같다면 i는 정수의 제곱으로 이루어진 완전제곱수이다.
• while 문을 이용하여 작성할 수도 있다.

 

예제

1부터 100까지의 수 중, 완전제곱수 찾기

#include <iostream>
using namespace std;

int main() {
    int k;
    
    for (int i = 1; i <= 100; i++) {
        for (k = 1; k * k < i; k++);
        
        if (k * k == i) {
            cout << i << endl;
        }
    }
    
    return 0;
}

1
4
9
16
25
36
49
64
81
100