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

문제 설명

1. 배열이 주어진다.

2. 배열의 숫자들은 1000이하의 서로 다른 숫자이다.

3. 배열의 숫자들 중 3개를 더해 소수가 되는 경우의 개수를 return하면 된다.

풀이 과정

 1. 아리스토텔레스의 체를 이용하여 해당하는 위치가 맞는지 구하면 된다.

 2. 1000이하의 서로 다른 수이기 때문에 최대 숫자를 1000+999+998이다. 체의 크기를 그걸 기준으로 정하면 된다.

 3. 숫자는 1부터 세고, 나는 보기 좋게 3000을 기준으로 잡았다.

코드

 

	import java.util.*;
	class Solution {
	public int solution(int[] nums) {
	int answer = 0;
	// 1000 999 998로 만드는 값이 최대, 걍 보기좋게 3000
	boolean num[] = new boolean[3000];
	// 아리스토텔레스의 체-------------------------
	for(int i=2; i<3000; i++){
	num[i] = true;
	}
	for(int i=2; i*i<3000; i+=1){
	for(int j=i*i; j<3000; j+=i){
	num[j] = false;
	}
	}
	//---------------------------------------------
	// 수 하나씩 작은것부터 만들면서 소수 판별하기
	Arrays.sort(nums);
	for(int i=0; i<nums.length-2; i++){
	for(int j=i+1; j<nums.length-1; j++){
	for(int k=j+1; k<nums.length; k++){
	int comp = nums[i] + nums[j] + nums[k];
	if(num[comp])
	answer++;
	}
	}
	}
	return answer;
	}
	}

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