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

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

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

 

	#include<bits/stdc++.h>
	using namespace std;
	bool IsPrime(int num){
	if(num==1) return false;
	if(num==2) return true;
	if(num%2 == 0) return false;
	for(int i=3; i<=sqrt(num); i++){
	if(num%i == 0) return false;
	}
	return true;
	}
	int solution(vector<int> nums) {
	int answer = 0;
	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(IsPrime(sum)) answer++;
	}
	}
	}
	return answer;
	}

view raw 소수 만들기.cpp hosted with ❤ by GitHub

주어진 배열에서 3개의 숫자를 고르면 되므로 3중 for문 이용

IsPrime이라는 소수 판별 함수를 사용하여 소수 판별

1일 경우는 무조건 소수가 아니니 예외 처리

2는 짝수 중 유일한 소수니 예외 처리

2로 나눠지면 소수가 아니니 예외처리

3으로 나눌 때부터 for문 사용해서 num의 제곱근까지 돌린다(제곱근까지 돌리면 충분하다고 한다)

-> 에스트라토네스의 체

이 때 어느 한 수로라도 나누어 떨어지면 소수가 아니므로 false 리턴

소수인 경우 answer++을 해준다