프로그래머스 - 소수 만들기

1. 처음 문제 풀었을 때

import java.util.Arrays;

class Solution {
	public int solution(int[] nums) {
		Arrays.sort(nums);
		int count = 0,sum = 0;
		int isPrime = 0;
		
		for(int i = 0; i<nums.length; i++) {
			for(int j = i+1; j<nums.length; j++) {
				for(int k = j+1; k<nums.length; k++) {
					count = 0;
					sum = nums[i]+nums[j]+nums[k];
					for(int n = 2; n*n<=sum; n++) {
						if(sum%n==0) {
							count++;
							break;
						}
					}
					if(count==0) {
						isPrime++;
					}
				}
			}
		}
		return isPrime;
	}
}

소수가 아니면 count가 올라가면서 for문이 break 되고 count가 1이므로 소수 isPrime 의 값이 올라간다.

count는 세번째 for 문이 돌아갈때 항상 초기화 되야 하므로 count = 0를 써주었다.

 

2. 두번째

 

class Solution {
    public int isPrime(int num){
        for(int i = 2; i*i<=num; i++) {
            if(num%i==0) {
                return 0; 
            }
        }
        return 1;
    }

    public int solution(int[] nums) {
        int answer = 0;
        int sum = 0;
        for(int i = 0; i < nums.length-2; i++){
            for(int j = i + 1; j < nums.length - 1; j++){
                for(int k = j + 1; k < nums.length; k++){
                    sum = nums[i] + nums[j] + nums[k];
                    answer += isPrime(sum);
                }
            }
        }
        return answer;
    }
}

for문은 똑같았다. 그렇지만 nums.length만큼 반복문이 돌아가지 않기 때문에 불필요한 반복 횟수를 줄였다.

 

isPrime이라는 소수를 구하는 메서드를 따로 빼서 소수면 1을 리턴하도록 하였고 이를 answer 변수에 더해주었다.

 

isPrime 반복문을 설명하자면 시작 지점을 2로 시작한 이유는 

 

소수의 정의를 알면 된다. 1과 자기 자신 이외로 나눠지지 않는 수가 소수이다.

 

굳이 1과 자기자신을 포함시켜서 나눌 필요는 없다. 2부터 나누면 된다.

 

조건은 num/2로 해도 가능, num 값에 Math.sqrt -> 루트를 구하는 함수를 써서 조건을 주어도 똑같지만

 

반복 횟수가 루트 값을 사용하는 것이 훨씬 효율적이다.

 

소수 구하는 공식 더 궁금하다면 ->>

https://eblee-repo.tistory.com/27

에브리 저장소