[JAVA] 자바 예제 - 소수(Prime Number) 구하기

<문제 >

1~ 50까지의 숫자 중에 소수만을 추출해서 출력하는 프로그램을 작성하시오.

 

 

문제 해결 포인트

 

소수란 1과 자기 자신의 숫자로만 나누어 떨어지는 수이다.

즉, 1과 자기 자신 이외의 숫자로 나누어 떨어지면 소수가 아니다.

 

 

문제 해결 과정

 

첫번째, count하기

1. 1부터 N(자기 자신)으로 나누어 나머지가 '0'인 횟수를 체크한다.   

   (이때, N이 증가할 때마다 count가 초기화 되어야 하므로 중첩 for문 외부에 작성)

2. 조건문을 통해 count가 2인 수를 출력하여 소수를 추출한다.

 

public class Count {
 
    
    public static void main(String[] args) {
        for(int i = 1; i <= 50; i++) {
            int count = 0;
            
            for(int j = 1; j <= i; j++) {
                if(i%j == 0) {
                    count++;
                }
            }
            
            if(count == 2) {
                System.out.println(i);
            }
       }
        
    }    //main
 
}    //class

 

 

 

---

 

 

두번째, 제곱근 사용하기

※ 제곱근이란? 어떤 수의 제곱근은 제곱하여 그 수가 되는 수를 가리킨다.

1. 2부터 50까지의 범위에서 소수이면 true, 소수가 아니면 false를 반환하도록 변수를 선언한다.

   (1은 소수가 아니므로 제외한다.)

2. i의 값을 2부터 Math.sqrt(i)까지의 범위로 나누어 떨어지면 소수가 아닌 수(false)가 된다.

   (ex. Math.sqrt(50) = 7.xxx이므로 Math.sqrt(i)의 범위는 2 ~ 7이 해당된다. )

3. i의 값이소수(true)일 때 출력한다.

 

public class SquareRoot {
 
    
    public static void main(String[] args) {
        for(int i = 2; i <= 50; i++) {
            boolean isPrimeNumber = true;
            
            for(int j = 2; j <= Math.sqrt(i); j++) {
                if(i%j == 0) {
                    isPrimeNumber = false;
                    break;
                }
            }
            if(isPrimeNumber) {
                System.out.println(i);
            }
        }
        
    }    //main
 
}    //class