약수의 개수

 

 

선형탐색으로 약수 개수 구하기

가장 기본적으로 쉽게 구현 가능하다.

심플하게 구현하면 1부터 자기 자신까지 돌아가면서 직접 나누어 떨어지는지를 체크하는 것. 

그러나 단순 계산만해봐도 O(N)의 복잡도를 갖는다.

 

for문

int count = 0;
for(int i = 1; i <= num; i++)
{
    if(num % i == 0)
        count++;
}
return count;

Linq

Enumerable.Range(1, n).Where(k => n % k == 0).Count();

 

제곱근만큼만 구하기

자연수 N이 존재할 때, 약수는 절대 N의 제곱근 초과 ~ N 미만의 수가 될 수 없다.

O(logN)의 복잡도를 가진다.

 

[ 왜 제곱근 이하일까 ]

1. 곱해서 값이 K가 되는 두 수 a와 b가 있다고 해보자.

2. a와 b  가 같을 때를 기준으로 약수 끼리의 곱은 대칭이다.

( 만약 K가 6이면  루트 6인 2.44를 기준으로 1 * 6 / 2 * 3 / 2.44 / 3 * 2 / 6 * 1 일 것이다. )
3. 따라서 제곱근을 기준으로 이하의 값만을 생각해도 된다.

int count = 0;
for (int i = 1; i * i <= n; i++) 
{
    if (n % i == 0)
        count++;
}
return count;

 

배수를 활용한 약수 갯수 구하기

약수는 배수의 반대개념을 활용한 풀이법.
시간복잡도는 nlog(n) 으로 표현된다.

int[] count = new int[number + 1];
for (int i = 1; i <= number; i++) 
{
    for (int j = 1; j <= number / i; j++) 
        count[i * j]++;
}

 

 

소수판별

소수판별은 약수와 동일하게 제곱근을 기준으로 대칭이기 때문에 제곱근 이하까지만 구하면 된다.

bool isPrime(int n) 
{
    if (n <= 1) 
    	return false;
        
    for (int i = 2; i * i <= n; i++) 
        if (n % i == 0) 
        	return false;
        
    return true;
}

 

추가적으로 '에라토스테네스의 체'가 존재한다.

- 특정 범위만큼 배열을 선언한다음 2의 배수를 제거, 3의 배수를제거, 4의 배수를 제거.... 하는 식으로 소거법으로 구하는 방법.

- 특정 범위내에있는 소수들의 갯수를 구할 때 사용한다.