프로그래머스 코딩테스트 연습 - 소수 만들기(Level 1)

programmers

 

문제

프로그래머스 코딩테스트 연습 - 소수 만들기(Level 1)

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

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

---

사용 알고리즘

- 에라토스테네스의 체

 

풀이

에라토스테네스의 체를 이용하여 미리 소수 목록을 구해놓고

n^3으로 가능한 모든 조합에 대해 세 수의 합이 소수가 되는 경우가 몇 개나 되는지 돌려본다.

 

나의 코드

#include <vector>
#include <iostream>
using namespace std;
int a[3001];
int solution(vector<int> nums) {
    int answer = 0;
    int i, j, k, len=nums.size();
    for(int i=2;i<=3000;i++){
        if(a[i]==1) continue;
        a[i]=2;
        for(int j=i*2;j<=3000;j+=i) a[j]=1;
    }        
    for(i=0;i<len;i++)
        for(j=i+1;j<len;j++)
            for(k=j+1;k<len;k++)
                if(a[nums[i]+nums[j]+nums[k]]==2) answer++;
    return answer;
}

 

남의 코드(좋아요 최다 코드)

#include <vector>
#include <iostream>
using namespace std;
bool check(int n){
    for(int i=2;i<n/2;i++)
        if(n%i==0)
            return false;
    return true;
}
int solution(vector<int> nums) {
    int answer = 0;
    int N=nums.size();
    for(int i=0;i<N;i++)
        for(int j=i+1;j<N;j++)
            for(int k=j+1;k<N;k++){
                if(check(nums[i]+nums[j]+nums[k]))
                    answer++;
            }
    return answer;
}