주어진 범위 내 모든 소수 구하기

 

    public static String listPrimes(int num) {
        // 2이상의 자연수를 입력받아 2부터 매개변수까지의 소수(prime number)들을 리턴
        String result = "2";

        for(int i = 3; i<=num; i+=2){
            boolean isPrime = true;
            int sqrt = (int) Math.sqrt(i);
            
            for(int j = 3; j<=sqrt; j+=2){
                if(i%j==0) isPrime = false;
            }

            if(isPrime) result += "-"+i;
        }
        return result;
//	output ex) "2-3-5-7-..."
    }

입력값은 최소 2이상 이므로 최종 출력물인 result에 "2"를 할당한다. 이로 인해 2는 항상 정해저 있으므로 반복문은 3부터 입력값까지 진행하며 2를 제외한 모든 짝수는 소수에서 제외되므로 2씩 더해가며 진행.

 

두번째 반복문또한 3부터 모든 짝수를 제외하고 진행된다. 모든 소수는 2부터 제곱근까지 약수가 존재 하지 않기 때문에 반복문의 범위는 3부터 시작하여 제곱근 까지이며 범위내의 숫자들을 반복하며 차례로 첫번째 반복문의 숫자에 나누어 떨어지는지 판별한다.

 

만약 두번째 반복문 진행중 나머지가 0인 값을 발견한다면 소수가 아니므로 위에 저장한 boolean 타입의 변수를 false로 재할당 해주고 나머지가 발생한다면 그대로 진행하여 결과값을 저장하는 변수에 추가해준다.