백준 1978번 - 소수 찾기

소수 찾기

문제

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

입력

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

4
1 3 5 7

출력

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

3

 

내 코드

package com.heejin.baekjoon.ex09;

import java.util.Scanner;

public class No1978 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    boolean[] sosus = sosus(1, 1000);
    int num = sc.nextInt();
    int count = 0;
    for (int i = 0; i < num; i++) {
      int a = sc.nextInt();
      if (!sosus[a - 1]) { 
        count++;
      }
    }
    System.out.println(count);
  }
  
  static boolean[] sosus(int min, int max) {
    boolean[] whole = new boolean[max - min + 1];
    if (min == 1) {
      whole[0] = true;
    }
    
    for (int i = 2; i <= max; i++) {
      for (int j = 2; j <= max / 2 ; j++) {
        if (i * j > max) {
          break;
        }
        if (i * j >= min) {
          whole[i * j - min] = true; 
        }
      }
    }
    return whole;
  }
}

파이썬으로 소수 문제들을 풀었을 때의 기억을 되짚어봤을 때, 소수를 구하는 방법은 소수의 정의를 그대로 따르는 방법, 즉 범위에 있는 모든 수에 1과 자기자신을 제외한 어떤 자연수로도 나눠떨어지지않는 지를 확인하는 방법, 그리고 에라토스테네스의 체....즉 범위에 있는 모든 수의 집합에서 자기자신을 제외한 2이상의 배수(2*2, 2*3, 2*4, 2*5..... 3*2, 3*3, 3*4, 3*5,....4*2, 4*3, 4*4, 4*5.....)들을 모두 제외하고 남은 수의 집합을 구하는 방법이 있다. 전자는 직관적이긴 해도, 백준 문제를 풀다보면 시간 초과라든지 메모리 초과라든지 뭐든 뜨게 된다. 확인하는 모든 수를 대상으로 그것이 그 이하의 수로 나눠떨어지는 지 모두 확인해야하기 때문이다. 가령 수를 한개만 확인하더라도 그 수가 엄청 크다면 2 이상 그 수 이하의 모든 수로 나누는 과정을 거쳐야한다. 따라서 후자가 전자보다 더 효율적일 수 있다.

 

내 기억에는 이 문제는 전자의 방법으로 얼마든지 풀 수 있었던 것 같다. 근데 어차피 후자의 방법으로 풀어야할 날이 올 것이기 때문에 처음부터 후자를 택했다. 내가 구현한 sosus라는 메서드는 최솟값 이상 최댓값 이하의 수들 중 소수가 아닌 것을 true로, 소수인 것을 false로 저장된 배열을 리턴한다. 소수인 것을 true로 소수가 아닌 것을 false로 할 수도 있었지만 일일이 모든 자리의 값을 true로 지정하기 싫었다.

 

아무튼 만약 5 이상 10이하의 수들 중에 소수를 구한다면 sosus(5, 10)는 [false, true, false, true, true, true] 배열을 리턴한다.

whole[0]	whole[1]	whole[2]	whole[3]	whole[4]	whole[5]
5	6	7	8	9	10
false	true	false	true	true	true

 

그런데 만약 최솟값이 1이라면 1은 소수가 아니기 때문에 1을 먼저 true로 변경하는 과정이 필수적이다.

 

이 문제에서는 일단 범위가 1이상 1000이하으로 주어졌기 때문에 sosus(1, 1000)의 리턴 배열을 받고 시작한다. 그리고 입력값들을 여러개 받으면 받은 배열에서 그의 값에 해당하는 인덱스 값이 false일 경우 count 를 하나씩 올리는 방식으로 답을 구한다.