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

https://programmers.co.kr/learn/courses/30/lessons/12977 

프로그래머스

 

풀이과정

소수 찾는 알고리즘은 에라토스테네스의 체를 사용했다.  
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;
}