[Programmers]소수 만들기 (Summer/Winter Coding(~2018))[Java]

문제 설명

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

 

제한사항

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

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

 

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

문제설명

하나하나 소수인지 판별하면서 계산하면 시간이 굉장히 오래걸리기 때문에 소수를 false, 소수가 아닌수를 true로 나타나는 boolean의 체를 생성해준뒤 나오는 위치에 따라서 분류해주도록 한다.

 

넘버값 하나가 1000이 최대이므로 3개를 더하면 3000이므로 3001이라는 최댓값에 에라스토테네스의 체를 만들어준뒤 3중 반복문을 통해서 3개를 더했을 때 위치값이 false라면 answer를 +=1해주도록 한다.

 

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 28 29 30 31 32 33 34 35 36 37 38 39 40

package algo; import java.util.*; import java.io.*;   public class Main {             public static int solution(int[] nums) {         int answer = 0;         //에라스토테네스의 체         boolean [] era = new boolean[3001];         //모든 소수 =false 소수가 아닌수 =true         for(int i=2;i<Math.sqrt(3001);i++) {                         if(!(era[i])) {                 for(int j=2;i*j<3001;j++) {                     era[i*j]=true;                 }             }         }         //합         for(int x = 0 ; x < nums.length-2 ; x++){             for(int y = x+1 ; y < nums.length-1 ; y++){                 for(int z = y+1 ; z < nums.length ; z++){                     if(!era[nums[x] + nums[y] + nums[z]]) {                         answer++;                     }                 }             }         }         return answer;     }          //문제풀이용 예시     public static void main(String[] args) {         int [] nums= {1,2,7,6,4};         System.out.println(solution(nums));     } }

cs

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

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