[완전탐색] 소수 만들기

문제 설명

int[] nums 중에 3개의 수를 더했을 때 소수가 되는 경우의 개수 구하기

풀이 순서
max 값인 3개를 더한 값으로 int[] 크기를 초기화

소수를 판별하는 메서드 생성

for문으로 완전탐색

소수 카운팅

 

내 풀이

xx

 

다른 사람 풀이 참고

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        boolean[] isPrime = isPrime(1000 + 999 + 998);
        int len = nums.length;
        for(int i=0; i<len-2; i++) {
            for(int j=i+1; j<len-1; j++) {
                for(int k=j+1; k<len; k++) {
                    int sum = nums[i] + nums[k] + nums[j];
                    if(!isPrime[sum]) {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
    
    private boolean[] isPrime(int n) {
        boolean[] isPrime = new boolean[n+1];
        
        isPrime[0] = false;
        isPrime[1] = false;
        
        for(int i=2; i <= Math.sqrt(n); i++) {
            if(!isPrime[i]) {
                for(int j=i*i; j<=n; j+=i) {
                    isPrime[j] = true;
                }
            }
        }
        
        return isPrime;
    }
}

 

새로 알게된 사실

 

소수 판별하는 방법

1. N을 N보다 작은 자연수로 모두 나누기
   

   public boolean isPrime(int n) {
       if (n <= 1) return false;
       for (int i = 2; i < n; i++) {
           if (n % i == 0) return false;
       }
       return true;
   }

   
   시간 복잡도는 O(N)
2. N의 제곱근보다 작은 자연수로 모두 나누기
   

   public boolean isPrime(int n) {
       if (n <= 1) return false;
       for (int i = 2; i <= Math.sqrt(n); i++) {// n의 제곱근까지 나누기
           if (n % i == 0) return false;
       }
       return true;
   }

   
   시간 복잡도는 O(√N)
   
3. 에라토스테네스의 체 이용하기
   

   public boolean[] isPrime(int n) {
       //0부터 n까지의 수이기 때문에 n+1 할당
       boolean[] isPrime = new boolean[n+1];
       
       //0과 1은 소수가 아니라 false를 저장
       isPrime[0] = false;				
       isPrime[1] = false;
       
       for(int i = 2; i <= Math.sqrt(n); i++) {
   		// 2부터 배수에 해당하는 수를 true로 변환한다.
   		for(int j = i * i; j < isPrime.length; j = j+i) {
   			isPrime[j] = true;
           }
   	}
       return isPrime;
   }

   
   시간 복잡도는 O(Nlog(log N))
   N이하의 소수를 판별하는 것만 따지면 O(NlongN)