유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단 a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다.
r = a % b
a = qb + r q = a/b 의 몫
gcd(a, b) = g
a = a'g, b = b'g → a' 와 b'은 서로소 (g가 최대공약수이기때문)
따라서
a'g = qb'g + r
(a'-qb')g = r
r도 g의 배수 → r = r'g
→ a'g = qb'g + r'g
고려해볼 점은 r' 과 b'이 다른 최소공배수를 가지고 있지 않을까
gcd(b,r) = g'
b랑 r 모두 g의 배수
g' = kg
a'g = qb'g + r'g → qb''kg + r''kg
그럼 이제 반대로 a'g 또한 kg의 배수가 된다.
a = a''kg
a''kg = qb''kg + r''kg
gcd(b, r) = g' 이고 b, r이 g의 배수인 kg라고 가정을 하면,
a''k = a', b''k = b' 에서 a'과 b'이 서로소라는 것에 모순이 생긴다.
k = 1일 수 밖에 없다.
따라서 gcd(b, r) = g' 이고 g' = kg 인데 k = 1 이므로
gcd(a, b) = gcd(b, r)과 같다.
세 개 이상의 정수의 최대공약수를 구하는 방법
N이 소수인가? 를 어떻게 판별할 것인가
가장 단순한 방법은 N이하의 정수들로 나눠서 0으로 나눠떨어지는 값이 있는 지 없는 지 확인하는 것이다.
코드로 작성해보자.
isPrime = true;
int n; // 소수인지 판별할 임의의 수 n
for (int i = 2; i < n; i++)
if ( n % i == 0 )
isPrime = false;
간단하다. 어허! 그런데 n까지 다 돌 필요가 있을까? n은 홀수 또는 짝수일텐데, n의 약수는 쌍으로 존재할테니 n/2 까지만 돌아도 되지 않을까?
그렇다면 n/3은? n/5는 ?
ex) N = 100
1 x 100 2 x 50 4 x 25 5 x 20 10 x 10
100 x 1 50 x 2 25 x 4 20 x 5
1 ~ 10 까지만 확인하면 그 이후는 어차피 쌍으로 존재하니 확인할 필요가 없는 것을 볼 수 있다.
그래서 우리는 N의 제곱근까지만 확인해보면 소수인지 아닌지를 판별할 수 있다.
이런 방법으로 수행하는 경우 O(√N)의 시간복잡도를 가지게 된다.
그래서 N이 소수인지 아닌지를 판별하는 코드는 수정하면 다음과 같다.
isPrime = true;
int N;
for (int i = 2; i * i <= N; i++)
if (N % i == 0)
isPrime = false;
소수를 판별하는 가장 빠른 방법은 N의 제곱근보다 작은 소수들로만 N을 나눠보는 것이다. 나눠보기 위한 소수 리스트를 구하기 위해서 에라토스테네스의 체를 이용한다.
이때 시간복잡도는 O(√N / ln(√N)) 이다.
N보다 작은 소수들의 목록을 찾기 위한 방법이다.
2부터 N까지 증가하면서 소수인지 판별한다.
소수이면 방문한 수의 배수들을 모두 방문 처리해준다.
int N;
boolean[] isPrime = new boolean[N]; //배열 초기값 false
for (int i = 2; i*i <= N; i++)
if (!isPrime[i])
for (int j = i*i; j < N; i + j)
isPrime[j] = true;
위 코드를 작성하면 isPrime 배열에서 false 값을 갖는 인덱스는 소수임을 구할 수 있다.
삼성sds 강의를 들으면서 소수 리스트를 생성하는 것을 배웠는데, 실제 코드를 작성하면 에러가 발생한다. 에러 발생 코드와 그 이유를 살펴본다.
int N;
boolean[] isPrime = new boolean[N]; //배열 초기값 false
ArrayList<Integer> primeNums = new ArrayList<>();
for (int i = 2; i <= N; i++)
if (!isPrime[i]) {
primeNums.add(i);
for (int j = i*i; j < N; i + j)
isPrime[j] = true;
}
소수를 저장한 리스트 primeNums를 생성해주고, isPrime이 false인 값을 갖는 인덱스 i를 primeNums에 추가해주려 하였다.
i는 최대 백만까지 증가한다. N보다 작거나 같기만 하면 통과하니 괜찮지만, 두번째 for문에서부터 문제가 발생한다.
j는 i x i 즉, 백만 x 백만의 숫자가 발생한다. j는 int형이기 때문에 오버플로가 발생하게 되어 음수의 값을 갖는다.
이로 인해 j < N
을 통과하지만 isPrime[j] = true;
에서 음수인 j는 isPrime의 인덱스 범위를 벗어나므로 에러가 발생하게 된다.
따라서 강의에서 알려준 코드는 잘못되었다. 실제로 내가 풀이한 문제 중 골드바흐의 추측 문제에도 작성하였지만 에러가 발생한다.
위 코드 말고 따로 게시판에 올려준 코드가 있다.
해당 코드는 정상 작동한다.
int P[] = new int[4000001];
int Plist[] = new int[1000001],Pcnt //Pcnt의 초기값은 0
for(i=2;i<=n;i++)
{
if(P[i]==0)
{
Plist[++Pcnt] = i;
for(j=i+i;j<=n;j+=i)
{
P[j]=1;
}
}
}
위 코드는 아마 옳게 작동할 것이다. 강사님이 풀이한 문제 코드를 가져오셨으니...
뿐더러 위 코드는 두번째 for문을 i*i
가 아닌 i+i
로 풀이하셨다. 그러니깐 에러가 안뜨지,,,,
위 코드의 작동 원리를 알고 있긴 한데, 익숙하지가 않아서 isPrime 배열에서 false인 인덱스를 따로 리스트에 저장하는 방법이 나에겐 편리하다.