정수론

WooHyeong·2023년 3월 9일
0

Algorithm

목록 보기
14/41

합동식

  • 항등식과 합동식
    합등식은 (=)로 그 관계를 나타내지만, 합동식은 합동기호(≡)로 관계를 나타낸다.
    합동식 a≡b(mod p)는 a와 b를 p로 나눈 나머지가 같다는 뜻이다.

합동식의 성질

  • a ≡ a (mod p)
  • a ≡ b (mod p) → b ≡a (mod p)
  • a ≡ b (mod p), b ≡ c (mod p) → a ≡ c(mod p)
  • a ≡ b (mod p) → a x c ≡ b x c (mod p)
  • a ≡ b (mod p) → a ± c ≡ b ± c (mod p)
  • a ≡ b (mod p), c ≡ d (mod p) →
    1. a + c ≡ b + d (mod p)
    2. ac ≡ bd (mod p)
  • a ≡ b (mod p) → a^n ≡ b^n (mod p)

유클리드 호제법

유클리드 호제법은 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)과 같다.

세 개 이상의 정수의 최대공약수를 구하는 방법

  1. 소인수분해
  2. a와 b의 최대공약수를 구하고 b와 c의 최대공약수를 구한다.

에라토스테네스의 체

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인 인덱스를 따로 리스트에 저장하는 방법이 나에겐 편리하다.

profile
화이링~!

0개의 댓글