[Java] 소수 출력하기

[Java] 소수 출력하기

---

문제: 1부터 100000 사이의 숫자 중, 소수만 출력해라.

 

코드

public class Main {
    public static void main(String[] args) {  //main method
        for(int n=2;n<=100000;n++){
            // 2,3, ...., sqrt(n) -> 루트 n까지만 검사.
            // n의 약수 중 루트 n보다 큰 두개의 약수가 존재할 수 없기때문
            boolean isPrime=true;
            for(int i=0;i*i<=n && isPrime;i++){
                if(n%i==0){
                    isPrime=false;
                }
            }
            if(isPrime){
                System.out.println(n);
            }
        }
    }
}

 

해설

-> 소수를 알아보기 위한 검색 범위: root(n)까지 검색하면 된다.

-> n의 약수 중에서 루트(n)보다 큰 두개의 약수가 존재한다고 가정 시, 두 개의 곱은 n을 넘게 됨으로 for문은 

   i제곱이 n을 넘지않을때까지 반복되면 된다.