약수

약수를 구하는 방법

1. 1부터 n까지 %연산을 활용하여 구하기

2. 1부터 루트n까지 %연산을 활용하여 구하기 

 

루트n까지만 비교해도 되는 이유는 약수는 짝을 지어 있기 때문이다.

약수의 개수가 홀수일 경우 root를 씌어준 값이 약수가 된다.(루트n까지 확인해야한다.)

 

시간복잡도 

1번 방법 : O(n)

2번 방법 : O(√n)

// 1번 방법 O(n)
int n = 121;

for(int i = 1; i <= n; i++){
	if(n%i == 0)
    	//약수 i와 n/i
}

// 2번 방법 O(√n)
int n = 121

for(int i = 1; i*i <= n; i++){
	if(n%i == 0)
    	 //약수 i와 n/i
}

 

 

약수와 배수

A = B*C

B는 A의 약수이다.

A는 B와C의 배수이다.