[구름LEVEL] 인싸가 되고 싶은 민수

난이도	정답률
★★	40.6%

 

구름LEVEL

문제

정수 a, b가 주어지면 a와 b를 포함하여 사이에 있는 모든 정수의 약수를 썼을 때 1을 제외하고 가장 많이 등장하는 약수를 구하는 프로그램을 작성하시오.

2 ≤ a, b ≤ 1,000,000,000

 

해결

key point, 어떤 길이 2 이상의 임의의 구간이 주어지면 그 구간 안에 n의 배수보다 2의 배수의 개수가 항상 많거나 같다.

1. a와 b가 다르면 2출력.
2. 같다면 a의 약수 중 가장 작은 값을 출력.

 

코드

#include <iostream>
using namespace std;
int a, b;
int leastDivisor(int num) {
    for (int i = 2; i * i <= num; i++) {
        if (!(num % i)) return i;
    }
    return num;
}
int main() {
    scanf("%d %d", &a, &b);
 
    if (a != b) printf("2");
    else printf("%d", leastdivisor(a));
 
    return 0;
}

후기

처음 문제를 풀 때 잘 못 읽고 a, b 두 수 의 약수 중 가장 작은 약수 구하는 문제로 이해하고 풀었을 때 어쩐지 80점이나 맞더니 정답에 2가 많기 때문이었다 ㅋㅋㅋㅋ

그 이후에 고쳤을 때는 이중for문때문에 시간초과... 뭔가 2일거 같다고는 생각했지만 확실하지 않아서 결국 비타알고를 확인했다. 비타알고 최고!!

goorm