#백준_2986 파스칼 - Java 자바

# 유형 : 구현

# 난이도 : 실버2

# 주어진 숫자 - 자기 자신을 제외한 가장 큰 자기자신의 약수 를 구하는 문제였는데, 주어진 알고리즘을 그대로 구현했더니 통과하였다. 시간초과는 발생하지않았는데, 발생한다면 에라토스테네스의 접근을 이용하여 해결할 수 있을것 같다.

 

** 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p2986 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        int count = 0;
        for(int i=N-1; i>0; i--) {
            count++;
            if(N%i==0)
                break;
        }
        System.out.println(count);
    }
}