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

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

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

 

 

계속 소수인지 확인하니깐

"에라토스테네스의 체"를 썼다. 

 

에라토스테네스의 체의 알고리즘은 내가 이해하기론 위키백과가 제일 좋은 것 같다. 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

간단하게 생각하면 

2의 배수 빼고, 3의 배수 빼고, 5의 배수 빼고, 다 빼면,,,

소수가 남아있는다. 

 

나는 프로그래머스를 오랜만에 해서 오류가 났는데 

오류가 Aborted (core dumped 에러) 가 났다. 

내 생각엔 check배열의 크기가 문제였다. ㅋㅎㅋㅎ...

세상에,,,

 

그래도 해결했당 ㅎㅎㅎㅎ

너무 신낭

 

 

<알고리즘>

에라토스테네스의 체를 사용해서 소수를 구한 뒤

3개의 숫자를 받아 숫자를 만든다(num)

확인한다. 

 

 

엉청 간단한데, 

에라토스테네스의 체가 문제가 아닌

나는 3개의 숫자를 받아서 숫자를 만들때, 

bfs를 사용해서,,

더 별로 였다,,

 

글너데 이런 방법을 사용하니 간단했다. 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int max_num = 0;

int solution(vector<int> nums) {
	int answer = 0;
	int check[1001] = { -1,-1,0,0,-1};
	for (int i = 2; i <= sqrt(1001); i++) {
		if (!check[i]) {
			for (int j = 2; i*j <= 1001; j++)
				check[i*j] = 1;
		}
	}
	for (int i = 0; i < nums.size(); i++) {
		for (int j = i + 1; j < nums.size(); j++) {
			for (int k = j + 1; k < nums.size(); k++) {
				int num = nums.at(i) + nums.at(j) + nums.at(k);
				if (check[num] ==0)
					answer++;
			}
		}
	}
	return answer;
}
int main() {
	vector<int> num = {1,2,7,6,4};
	
	cout << solution(num);
}

이 코드는 비쥬얼에서 한번 실행해본다고,ㅎㅎㅎ

 

main까지 있는 것이다. ㅎㅎ