[TIL] 26/09/23 - 소수와 합성수

package Lv3;

import java.util.ArrayList;

import static Lv3.makePrimeNum.Solution.solution;

public class makePrimeNum {
    class Solution{
        static public int solution(int[] nums){
            //짝짝홀 홀홀홀
            int answer = 0;
            ArrayList<Integer> arr = new ArrayList<>();
            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++){
                        int sum = nums[i]+nums[j]+nums[k];
                        if(sum%2==1||sum==2){
                            boolean isPrime = true;
                            for(int q=2; q*q<=sum; q++){
                                if(sum%q==0){
                                    isPrime = false;
                                    break;
                                }
                            }
                            if(isPrime) answer++;
                        }
                    }
                }
            }
            return answer;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,7,6,4};
        System.out.println(solution(arr));
    }
}

문제

3개를 뽑아서 소수를 만들 수 있는가?
그럼 3개를 뽑은 수가 홀수인 경우를 찾아봐야한다.
그럼 짝짝홀 / 홀홀홀 의 경우밖에 없다

소수와 합성수

소수는 약수를 자기자신과 1만 갖는 수를 말한다
합성수는 1과 자기자신을 제외하더라도 다른 약수가 존재하는 수다

합성수(약수가 존재하는지)인지 검사해서 하나도 안걸리면 소수라고 판단하는 귀공법 형태

의문점

for(int q=2; q*q<=sum; q++){
                                if(sum%q==0){
                                    isPrime = false;
                                    break;
                                }
                            }

처음엔 이 부분을 q<=sum 까지 다 돌리는 방식으로 작성했는데,
다른 사람들의 풀이방식에서는 위처럼 q**q<=sum으로 작성했다

해당 부분에 q*q를 sum 이하까지 반복하는 이유는 무엇일까?
어떤 수 N의 약수들이 가지는 대칭성 때문이다

예를들어 N이 36이라고 해보자
36의 약수로는 1,2,3,4,6,9,12,18,36
여기서 규칙을 볼 수 있다, 가장 좌측과 가장 우측의 곱이 36으로 이어진다는 것
6을 중심으로 해서 좌 우로 나뉘는 숫자들을 잘 살펴보면
1,2,3,4 | 9,12,18,36
왼쪽은 루트 36(=6)보다 작고, 우측은 루트 36보다 크다

즉, 어떤 수가 합성수일 경우에는 어떤 약수가 최소 루트N 이하에 무조건 들어있다
이를 통해 전체를 검사하는 것보다 훨씬 시간을 줄일 수 있다
O(N) -> O(루트N)