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

나머지 연산

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

 - 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

단일 테스트케이스

17425번: 약수의 합

- 미리 구해놓자.

최대 공약수

두 수가 주워졌을때 공통으로 같는 약수 중에서 가장 큰 수
만약 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번: 최대공약수와 최소공배수

소수

소수 구하는 방법
 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번: 골드바흐의 추측

이건 설명이 아닌 정리.