[Algorithm] 약수 구하기

for(int i = 1; i <= n; i++)
{
	if(n % i == 0)
    	  cout << i <<endl;
}

• 가장 기본적인 약수 구하는 로직이다.
• O(n)의 속도를 가진다.
• 조금만 복잡한 약수 알고리즘 문제가 나온다면 시간 초과로 사용하지 못할 것이다.

 

1의 약수 : 1                        √1 : 1

2의 약수 : 1,2                     √2 : 1.4142

3의 약수 : 1,3                     √3 : 1.7320

4의 약수 : 1,2,4                  √4 : 2

5의 약수 : 1,5                     √5 : 2.2360

6의 약수 : 1,2,3,6               √6 : 2.4494

7의 약수 : 1,7                     √7 : 2.6457

8의 약수 : 1,2,4,8               √8 : 2.8284

9의 약수 : 1,3,9                  √9 : 3

10의 약수 : 1,2,5,10           √10 : 3.1622

 

• 위의 수를 분석해보면 서로 대칭인 점을 알 수 있다.
• n의 루트값을 기준으로 대칭이다.

 

for(int i = 1; i*i <= n; i++)
{
    if(n % i == 0)
    {
    	if (n / i == i)
                cout << i << endl;
        else
                cout<< i << " " << n / i << endl;
    }	  
}

• 위의 특징으로 구현한 알고리즘이다.
• O(√n)의 속도를 가진다.