[백준 BOJ 1978번] 소수 찾기

출처 : https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

1. 문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

---

2. 입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

4
1 3 5 7

---

3. 출력

주어진 수들 중 소수의 개수를 출력한다.

3

---

4. 풀이

이 문제의 가장 핵심은 소수를 찾는 것이다. 이를 찾는 방법 2가지를 찾아보았다.

 

1. 배수를 활용한 정답지 만들기

이 방법은 범위 내의 숫자들 중 미리 소수를 찾아내고 이들 인덱스의 Boolean 배열의 값은 True, 소수가 아닌 index는 False로 둔 다음에 주어지는 숫자들에 대해 T/F 검사만 진행하여 소수 판별을 하는 것이다. 

 

2. 약수를 활용하여 걸러내기

일단 위 방법과 달리 소수인지 여부를 아예 모르고 있는 상태에서 주어지는 임의의 숫자 A에 대해서 2부터 A-1까지 나눠보는 방식이다. 만약 나누어 떨어지는 숫자가 있다면 A는 그 숫자의 배수이므로 소수가 아니게 되는 것이다.  

---

5. 소스코드

1. 배수를 활용한 정답지 만들기

import java.io.*;
import java.util.*;
class Main{
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //N은 받아올 숫자 개수
        int [] nums = Arrays.stream((br.readLine().split(" "))).mapToInt(Integer::parseInt).toArray(); //받아온 숫자들에 대한 배열 nums
        
        Boolean [] tf = new Boolean[1001]; //true false 구분할 boolean형 배열

        for(int i=0; i<1000; i++) tf[i] = true; //tf배열 true로 초기화

        for(int i=2; i<=500; i++){  // i의 배수들은 모두 false화
            for(int j=2; j<=500; j++){ //i에 대한 배수 정의를 위한 for문
                if(i*j>1000) break;
                tf[i*j] = false; //i*j는 소수가 아니므로 인덱스가 i*j-1인 tf는 false값 넣어줌.
            }
        }
        tf[1] = false;

        int count = 0;

        for(int i=0; i<N; i++){
            if(tf[nums[i]] == true) count += 1;
        }

        System.out.println(count);

    }
}

2. 약수를 활용하여 걸러내기

import java.io.*;
import java.util.*;
class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int N = Integer.parseInt(br.readLine());
    int [] nums = Arrays.stream((br.readLine().split(" "))).mapToInt(Integer::parseInt).toArray();
    int count = 0;
    for(int i=0; i<N; i++){
      count += 1; //
      if(nums[i]==1) count -=1;
      else{
        for(int j=2; j<nums[i]; j++){ //주어진 수보다 작은 수들 중 1을 제외하고 나눠떨어지는 경우가 하나라도 존재하면 소수가 아니다.
          if(nums[i]%j==0) {count -=1; break;}
        }
      }
    }
    sb.append(count);
    System.out.println(sb);
  }
}

---

6. 배운 것

int [] nums = Arrays.stream((br.readLine().split(" "))).mapToInt(Integer::parseInt).toArray();

라는 식을 활용한다면 띄어쓰기를 적용하여 한 줄에 입력한 데이터들을 String형 배열에 넣고 그걸 다시 int형 배열로 옮기는 수고를 줄일 수 있다.