나머지 연산, 약수 , 최대 공약수, 소수

반응형
반응형

나머지 연산

3 % 2 = 1

말한다.

위 식은 다음과 같다.

((2%2) + (1%2) %2 ) => (0 + 1) % 2 => 1

곱하기도 가능하다.

((3%2) * (1%2) %2 ) => (1 * 1) % 2 => 1

하지만 아쉽게도 나눗셈은 되지 않는다.

사실 나머지 연산을 중심으로 하는 문제는 거의 없다.
다만 이것은 주로 숫자가 너무 커서 나눠야 되는 상황에 유용하다고 한다.
대표적인 문제 
www.acmicpc.net/problem/4375

 

4375번: 1

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

www.acmicpc.net

 - 1로만 이뤄졌다는 뜻은 1, 11,111,1111을 말한다.

약수

약수는 나누어지는 수를 뜻한다.

8의 약수를 구한다고 한다면 1, 2, 4, 8이 8의 약수가 된다.

약수 아이디어 
2가 8의 약수라면 2/8 도 8의 약수다.
이를 활용하면

for(int i = 1;i<=root(n);i++) {
   if(n%i) {
     System.out.println(i);
     System.out.println(n/i);
   }
}

root를 구하는 이유는 절반을 구하기 위함이다.
하지만 이 방법은 root가 int가 아닐 수 있기 때문에 조금더 정확히 풀려면

for(int i = 1;i*i<=n;i++) {
   if(n%i) {
     System.out.println(i);
     System.out.println(n/i);
   }
}

라고 하면 된다.
이를 활용한 문제로는

 

17427번: 약수의 합 2

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더

www.acmicpc.net

단일 테스트케이스

 

17425번: 약수의 합

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더

www.acmicpc.net

- 미리 구해놓자.

최대 공약수

두 수가 주워졌을때 공통으로 같는 약수 중에서 가장 큰 수
만약 1이 등장하면 서로소

for(int i = 2;i<=Math.min(2,10);i++) {
        if(2%i == 0 && 10 % i == 0) {
          System.out.println(i);
   }
}

유클리드 호제법

public int gcd(int a,int b) {
  if(b == 0) {
  	return a;
  }
  return gcd(b,a%b);
}

최소 공배수

(a / gcd * b / gcd) * gcd

즉 a*b/gcd같은말.

이를 활용한 문제로는

 

2609번: 최대공약수와 최소공배수

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

www.acmicpc.net

소수

소수 구하는 방법
 x를 2부터  n까지 전부 나눠준다.
 x를 2부터 root(n)까지 전부 나눠준다.
 

에라스토테네스의 체

 boolean[] check = new boolean[b+1];
    check[0] = check[1] = true;
    for (int i = 2; i*i <= b; i++) {
      if(check[i]) {
        continue;
      }
      for(int j = 2*i; j<=b;j+=i) {
        check[j] = true;
      }
    }

check에 모든 배수를 넣어준다. 어차피 소수가 아니니까.

 

6588번: 골드바흐의 추측

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰

www.acmicpc.net

이건 설명이 아닌 정리.

'알고리즘 > 코테 알고리즘 정리 노트' 카테고리의 다른 글

나머지 연산, 약수 , 최대 공약수, 소수  (0) 2021.02.18
LinkedList  (0) 2020.12.06
배열 90도 회전 (코드만 존재 설명 X)  (0) 2020.10.29
숫자 회전 (4자리 한정)  (0) 2020.10.20
위상 정렬  (0) 2020.10.01
크루스칼 알고리즘  (0) 2020.10.01

댓글(0)

Designed by JB FACTORY