[C++] 알튜비튜 3주차 - 정수론

• 정수론이란?
• 각종 수의 성질을 다룬다.
• 약수 배수 최대공약수 최소공배수 소수 판결

최대공약수

• 소인수분해 이용 - 두 수 중 작은 수 기준으로 돌리면서 가장 큰 공통 약수 구하기
• 구현 까다로움, 시간복잡도 O(n)
• 유클리드 호제법: 시간복잡도 O(log(n))
  • 기본 원리
    • A와 B의 최대공약수 = A-B 와 B의 최대공약수
      • A = a*G
      • B = b*G(a와 b는 서로소)
      • A - B = a*G-b*G = (a-b)*G
        • (a-b)와 b 또한 서로소 -> A-B 와 B의 최대공약수도 G
          • 이미 gcd⁡(a,b)=1 이므로, 어떤 정수 x,y 가 존재해서 ax+by=1을 만족시킨다.
          • 그럼 (a−b)x+by=1도 만족. 어떤 정수 조합으로 1을 만들 수 있으니까 gcd(a−b,b)=1 이 된다.
      • GCD(A,B) = GCD(A-B,B) -> A,B의 차이가 크면 오래걸린다.
    •  A와 B의 최대공약수 = A%B와 B의 최대공약수
      • A = a*G
      • B = b*G(a와 b는 서로소)
      • A = q*B+r(q=A/B의 몫, r=A%B)
      • r(A%B)=a*G - q*b*G =(a-q*b)*G -> (a-q * b)와 b 또한 서로소이므로 A%B와 B의 최대공약수도 G
      • GCD(A,B) = GCD(A-B,B) = GCD(A-2B, B) = ... = GCD(A%B2B)
    • 과정
      • 두 정수 a,b가 주어짐 (a>b)
      • a와 b의 최대공약수는 a%b와 b의 최대공약수와 같음
      • a%b를 구한 후 왼쪽 값, 오른쪽 값이어야 하므로 a%b와 b의 위치를 바꿈
      • b가 0일 때, a의 값이 최대공약수

int gcdIter(int a, int b){
	while (b) { // b == 0, a가 최대공약수
    	a%=b; // a=a%b;
        swap(a,b);
     }
      return a;
  }

 

소수

• 2~n까지 돌리면서 나눠지는 수가 없는지 판단 -> O(n)
• 2~ 루트n까지 돌리면서 나눠지는 수가 없는지 판단 -> O(루트n)

--> a=n/(루트n 이상의 수)라는 a가 존재한다면, a는 2이상 루트n 이하다(n%a=0)

--> 따라서 루트 n까지만 확인하면 그 이상은 확인할 필요 x

 ----> n이 큰 상황에서 2~n 사이에 존재하는 모든 소수를 구해야 한다면?

에라토스테네스의 체

• 각 수가 소수인지 판단한 여부를 저장하는 배열 사용
• 2부터 시작해서 해당 숫자의 배수에 해당하는 숫자들을 지워나간다.(~루트n)
• -> 약수가 존재하면 소수 x
• O(nlog(logn)) 만에 2~n까지 수에 대해 소수 판정 가능

이런 식으로!

결과

void isPrime(int n, vector<bool> &is_prime){
	//0과 1은 소수가 아니므로 먼저 제거
    is_prime[0] = is_prime[1] = false;
    //2~ 제곱근 n까지 검사
    for(int i=2; i<=sqrt(n); i++){
    	if(is_prime[i]){
			for(int j=i*i; j<=n; j+=i){ //i*i부터 시작하는 이유: i전까지의 수는 이미 전에 걸러짐
            	is_prime[j]=false;
                }
                }
                }
                }

• 에라토스테네스의 체의 과정 활용:
  • 소수 판단 여부 정보가 아닌, 어느 소수의 배수로 지워졌는지 저장.
  • 이미 값이 존재한다면 갱신 x
  • 결국 해당 인덱스의 가장 작은 소인수가 저장

 

 

정리 

• 유클리드 호제법 : 최대공약수 빠르게 찾기
• 에라토스테네스의 체: 대량의 소수를 빠르게 판별
• 에라토스테네스의 체는 2~루트n까지 검사. (단 문제에서 어떻게 활용하느냐에 따라 예외 존재)