[프로그래머스][Level1] 소수 만들기 c++

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

문제

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

풀이 과정

소수 찾는 알고리즘은 에라토스테네스의 체를 사용했다.
3개의 수를 더할 때는 3중 for문을 사용하여 더해주었고,
더한 값을 num 배열에 담았을 때 0이 아니면 소수이므로 카운트해준다.

풀이1

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

const int NUM = 3000;
int num[NUM];

void PrimeNum(){
    for(int i = 2; i <= NUM; i++){
        num[i] = i;
    }
    for(int i = 2; i <= sqrt(NUM); i++){
        if(!num[i]) continue;
        for(int j = i * i; j <= NUM; j += i){
            num[j] = 0;
        }
    }
}

int solution(vector<int> nums) {
    int answer = 0;
    PrimeNum();
    for(int i = 0; i < nums.size() - 2; i++){
        for(int j = i + 1; j < nums.size() - 1; j++){
            for(int k = j + 1; k < nums.size(); k++){
                int sum = nums[i] + nums[j] + nums[k];
                if(num[sum]) answer++;
            }
        }
    }
    return answer;
}

풀이2

#include <vector>
#include <iostream>
using namespace std;

const int NUM = 3000;
int num[NUM];

// sqrt 함수 구현
int sqrt(int n){
    int s = 0;
    int t = 0;
    s = n / 2;
    while(s != t){
        t = s;
        s = ((n / t) + t) / 2;
    }
    return s;
}

void PrimeNum(){
    for(int i = 2; i <= NUM; i++){
        num[i] = i;
    }
    for(int i = 2; i <= sqrt(NUM); i++){
        if(!num[i]) continue;
        for(int j = i * i; j <= NUM; j += i){
            num[j] = 0;
        }
    }
}

int solution(vector<int> nums) {
    int answer = 0;
    PrimeNum();
    for(int i = 0; i < nums.size() - 2; i++){
        for(int j = i + 1; j < nums.size() - 1; j++){
            for(int k = j + 1; k < nums.size(); k++){
                int sum = nums[i] + nums[j] + nums[k];
                if(num[sum]) answer++;
            }
        }
    }

    return answer;
}