[C/C++]프로그래머스 소수 만들기

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

 

소수를 판별하는 방법만 알면, 비교적 간단하게 풀 수 있다.

소수를 판별하는 방법에서는 여러가지 알고리즘이 있지만, 여기서는 제곱근을 이용하는 방법을 사용했다.

 

제곱근을 이용한 소수 판별

어떤 곱으로 이루어진 수는 제곱근을 기준으로 대칭적으로 구성됩니다.
12를 예로 들어봅시다.
12의 약수는 [1, 2, 3, 4, 6, 12] 입니다. 여기서 1과 자기자신인 12를 제외하면, [2, 3, 4, 6] 입니다.
남은 약수로 곱을 구성하면 , 2 X 6, 3 X 4, 4 X 3, 6 X 2 의 조합이 나오는데 12의 제곱근, 3.46이라는 숫자를 기점으로

대칭적으로 나뉘게 됩니다.
다라서 N이라는 어떤 수의 소수 여부를 판별할 때, 1부터 N-1 까지 나눠서 0이 나오는지 판별할 필요 없이
1부터 sqrt(N) 까지만 나눠서 0인지 아닌지 판별하면 됩니다.

 

따라서, 시작복잡도는 O(sqrt(N))이 됩니다. 

 

 

소스코드

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <math.h>

#define TRUE 1
#define FALSE 0

/********소수판별 함수***************/
int IsPrime(int Num)
{
    if(Num == 1) return FALSE; //1은 소수아님
    if(Num == 2) return TRUE; //2는 유일한 짝수인 소수
    
    if(Num%2 == 0) return FALSE; //2를 제외한 짝수는 소수가 아님.
    
    for(int i=3; i<=sqrt(Num); i++){
        if(Num%i == 0) return FALSE;
    }
    return TRUE;
}

// nums_len은 배열 nums의 길이입니다.
int solution(int nums[], int nums_len) {
    int count = 0;
    int sum=0;
    
    for(int i=0; i<nums_len - 2; i++){
        for(int j=1+i; j<nums_len-1; j++){
            for(int k=1+j; k< nums_len; k++){
                
              sum = nums[i] + nums[j] + nums[k];
                
                if(IsPrime(sum) == TRUE)
                    count +=1;
            }
        }
}   
    return count;
}