정수론

에라토스테네스의 체

• 소수를 찾는 효율적인 방법 중 하나.
• 소수(prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수.
• 즉 1과 자기 자신 외에 약수가 존재하지 않는 수.
• 시간 잡도 : O(nlog(log n))

  과정

  1. 2부터 시작하여 차례로 배수들을 제거하면서 소수를 찾는다.
  2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. 이 수는 소수이다.
  3. 이 소수의 배수를 모두 지운다.
  4. 위 과정을 반복한다.

  // 1~ 1_000_000 까지의 소수 구하기
  int end = 1_000_000;
  int[] sieve = new int[end+1];
  for (int i = 2; i <= end; i++) {
      sieve[i] = i;
  }
  for (int i = 2; i <= Math.sqrt(end); i++) {
      if(sieve[i] == 0){
          continue;
      }
      for (int j = i + i; j <= end; j += i) {
          sieve[j] = 0;
      }
  }
  for(int i = 2; i <= end; i++){
    if(sieve[i] != 0){
        System.out.println(i);
    }
  }

오일러 피

• 오일러 피 함수P[n] 의 정의는 1부터 n까지의 범위에서 n과 서로소인 자연수의 개수.
• 서로소란 두 자연수의 겹치는 소인수가 1 밖에 없는 수.

  과정

  1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화.
  2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(소수일 때) 현재 숸택된 숫자(K)의 배수에 해당하는 수를
     배열에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다.(i는 K의 배수)
  3. 배열의 끝까지 ii를 반복하여 오일러 피 함수를 완성한다.

유클리드 호제법

• 두 수의 최대 공약수를 구하는 알고리즘.
• 큰 수를 작은 수로 나누는 MOD 연산 수행.
• 작은 수와 MOD 연산 결과값(나머지) 로 MOD 연산 수행.
• 나머지가 0이 되는 순간의 작은 수가 최대 공약수.

  // a,b 의 최대공약수
  int Euclidean(int a, int b) {
    if (b == 0)
        return a;
    return Euclidean(b, a % b);
  }

확장 유클리드 호제법

• 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면, 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것.

  핵심 이론

  • 해를 구하고자 하는 방정식 : ax + by = c (a,b,c,x,y 는 정수)
  • 위 방정식은 c % gcd(a,b) = 0 인 경우에만 정수해를 가짐.
  • 다시 말해 c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가짐.
  • 이는 ax + by = c가 정수해를 갖게 하는 c의 최솟값이 gcd(a,b)를 의미.

  과정

  • 5x + 9y = 2 일 때 이 식을 만족하는 정수 x,y
  1. 5x + 9y가 정수해를 갖게 하는 c의 최솟값이 gcd(5,9) 라는 것을 적용. 5x + 9y = 1로 식을 변경.
  2. a,b(5,9) 로 유클리드 호제법을 반복 실행하며 몫, 나머지를 저장. 반복은 나머지가 0 이 되면 중단.
  3. 반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가며 x = y', y=x'-y'*q 를 계산.
     x',y' 는 이전 x,y 값을 의미하고, q는 현재 보고 있는 몫을 의미. 이때 처음 시작하는 x,y는 이전 x,y가 없으므로 1,0으로 지정하여 역계산 진행.
  4. 재귀 방식으로 알아낸 최종 x,y는 ax+by = gcd(a,b)를 만족. 그리고 c / gcd(a,b) = K 를 가정하면 최초 방정식의 해는 Kx,Ky.
  5. 과정 iii 에서 찾은 x는 2, y는 -1이므로 2/1 = 2 이며, 22, 2-1에 의해 최초 방정식의 해는 4,-2.