소수 만들기 프로그래머스(c++)

문제 설명

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

제한사항

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

1. 먼저 에라토스테네스의 체를 이용해 배열 50000크기의 소수 판별 행렬을 만들어준다.

50개 이하의 자연수, 각각 1000이하라고 했으므로 50000이면 충분

 

2. 3중 for문을 돌려서 score를 더한다.

3개를 더한 후 그 수가 소수인지 판별 소수면 answer++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <vector> #include <iostream> using namespace std;     bool era[50000]; void erathos() {     for(int i=2;i<50000;i++)         for(int j=2;j*i<50000;j++)             era[i*j] = true; }   int solution(vector<int> nums) {     erathos();     int answer = 0, size = nums.size(),score;     for(int i=0;i<size;i++)         for(int j=i+1;j<size;j++)             for(int k=j+1;k<size;k++)             {                 score = nums[i] + nums[j] + nums[k];                 if(!era[score]) answer++;             }                        return answer; } Colored by Color Scripter

cs