특정 숫자 n 까지의 약수 구하기, GCD [C++]

[문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 유클리드 호제법, 최대공약수 구하기, GCD [C++]

 

위 글도 참고하면 좋다.

 

아무튼 특정 숫자의 약수를 구하기 위해서는 약수의 정의부터 알 필요가 있다.

 

일반적으로

b=an인 정수 n이 존재할 때, a|b라 하고, 이때의 a를 b의 약수라 한다.

다르게 말하면 어떤 정수를 나누어 떨어지게 하는 0이 아닌 정수라고 한다.

 

모든 자연수는 최소한 1과 자기 자신을 약수로 갖는다.

**소수는 최소한의 약수만을 가진 1을 제외한 자연수를 말한다.

다시 말해서 약수가 1과 자기 자신뿐인 자연수를 말한다.

 

**합성수는 1과 자기자신 외에 다른 약수를 가지면 즉, 약수가 3개 이상이면 합성수라고 할 수 있다.

다시 말하면 소수들의 곱으로 이루어진 수라고 할 수 있다.

 

---

 

성질에는 몇가지가 있다.

y가 x의 약수이고 z가 y의 약수이면 z는 x의 약수이다.

a가 y와 z 모두의 약수이면 a는 y+z의 약수이다.

이건 당연한 것이고..

 

또 가장 중요한 성질 중 하나가

모든 합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다.

어떤 큰 수를 소인수분해 할 때, 그 수의 제곱근 보다 큰 수로 나눌 필요는 없다는 사실을 알 수 있다.

즉, 여기서 연산횟수를 엄청나게 줄일 수 있다.

 

 

---

 

이제 프로그래밍에서 약수를 구해보자.

 

for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            vec.push_back(i);
            if(n/i != i)vec.push_back(n/i);
        }
    }

n의 약수를 구하는 과정이다.

n이 125라면

우리가 알고 있는 약수는 1,5,25,125다.

i*i 가 125가 초과되려면 12까지만 조사한다.

즉, 1,5는 i가 되어 들어가고

125,25는 n/i로 되어 들어가서 

4개의 약수가 모두 구해진다.

 

그렇다면 i*i를 써야하느냐? 아니다.

물론 <cmath> 를 include하고 난 뒤 sqrt를 쓸 수 있다.

...
int arr10000000];
cnt = 0;

....


root = sqrt(N);// square root를 써도 된다.
for (i = 1; i <= root; i++) {
	if (N % i == 0){
    arr[cnt++] = i; // 작은수 저장
	if (N / i != i) arr[cnt++] = N / i; // 중복되는 경우 피하기 위함. 4/2 = 2이므로 2번 추가됨.
	} 
}

 

 

**여기서 핵심은 나눴을 때 중복을 피하기 위해 if문을 넣어주는 것이 좋다 이말이다.

 

여기서 제곱근보다 작거나 같은 약수를 갖는다를 이용했다.

 

그래서 시간을 줄일 수 있었다.

 

 

 

아니면 약수의 개수만을 원한다면

약수의 개수를 저장해놓는 방법도 있다.

#include<iostream>
using namespace std;

int cnt[100001]; //약수의 개수를 저장
int main() {
	int n;
	cin >> n;
    
	//1~n까지의 약수구하기
	for (int i = 1; i <= n; i++) {
        //i의 배수인 j들에 대해 약수의 개수를 1씩 증가
		for (int j = i; j <= n; j=j+i) {
			cnt[j]++;
		}
	}
    
}

 

약수의 개수를 저장하는 방식도 꽤나 유용한데..?

소수는 약수를 2개만 갖고있기 때문이다.