최대, 최소공배수 그리고 소수

최대공약수(GCD)

두 수 a,b의 공통된 약수중 가장 큰 수

 

- 구하는 방법

1. 2부터 시작해서 a,b로 공통되게 나누어 떨어지는 것중 최대값을 구한다. O(n) -> n은 a,b중 최소값

2. 유클리드 호제법을 사용하기

// 나는 주로 재귀를 사용하는 편
public int gcd(int a, int b){
	if(a%b == 0)
    	  return b;
	return gcd(a,a%b);
}

//반복문을 사용하여 구할수도 있음
public int gcd(int a, int b){
	int temp;
	while(true){
    	if(a%b == 0)
        	return b;
        temp = a % b;
        a = b;
        b = temp;
    }
}

위 코드는 유클리드 호재법을 사용해서 구현해본 코드이다. 

 

최소공배수(LCM)

- 최소공배수는 최대공약수를 사용하면 된다.

a,b의 최소 공배수 = g*(a/g)*(b/g)

*서로소 : a,b의 최대공약수가 1인 경우 두 수는 서로소이다. 

 

3가지 수 이상의 최대공약수, 최소공배수

- 3가지 이상의 수의 최대, 최소공배수는 두 수씩 묶어서 계산해주어도 동일하다.

 

소수

소수는 약수를 1과 자기자신만 같은 수

1. 값 하나가 소수인지 확인하는 경우

- n이 소수인지 확인하려면 1부터 n-1까지 약수가 있는지 확인하면 된다. O(n)

- 약수는 짝이 있으므로 1부터 √n까지만 확인하면 된다. O(√n)

*이 때 비교연산시√n까지는 i*i <= n의 비교 연산을 사용해 실수를 사용하지 않도록 해주는게 좋다.

2.  범위의 소수를 찾는 경우

- 약수의 성격을 빌리면 O(n√n)의 시간복잡도로 계산 가능하다.

- 에라토스테네스의 체

int n = maxNum; // n까지 중에 소수 찾기
boolean[] remove = new boolean[n+1] //소수가 아닌 수 체크
int[] sosu = new int[n] // 소수 넣기
int sn = 0; //소수의 개수

/* 소수로 지워주기
이 때, 제곱수부터 지우는 이유는 2부터 시작하여 작은 소수부터 지워줘서
11을 사용해 지울 때 11*2는 2*11때 지웠기 때문에 11*11 부터 지워주면 됨
지워진 수가 아니면 소수이므로 소수로 추가해주고 배수만큼 또 지워주기*/
for(int i = 2; i*i <= n; i++){
	if(remove[i])
    	continue;
        
    sosu[sn++] = i;
    for(int j = i; j*i <= n; j++){
    	remove[i*j] = true;
    }
}

> 소수로만 지워주면 되고

> 제곱수부터 시작하면 되는것이 포인트이다.(굉장히 많이 줄일 수 있음)