[백준] BJ S4 1978 소수찾기 (java)

www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

풀이

 

1) 범위내의 자연수 크기(1000)의 boolean 형 배열 isPrime을 선언한다.

2) 0과 1은 소수가 아니므로 2부터 1000까지 isPrime을 true로 설정한다.

3) 2부터 에라토스테네스의 체를 적용하여 isPrime을 false로 걸러준다.

4) 주어진 N개의 수를 뽑아 배열의 인덱스에 대입했을 때 true 면 answer++

5) answer 출력

 

주의 사항

 

1) 이 문제는 시간초과날 일도 없지만 범위가 넓은 다른 문제였다면 완전탐색 시 시간초과가 날 수 있다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * @author yhs
 * @date 2021. 4. 11
 * @see 
 * @mem
 * @time
 * @caution
 * [고려사항] 
 * [입력사항] 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
 * [출력사항] 주어진 수들 중 소수의 개수를 출력한다.
 */
public class BJ_S4_1978_소수찾기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N;
	static boolean isPrime[]; 
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		tokens = new StringTokenizer(input.readLine());

		isPrime = new boolean[1001];
		for(int i=2; i<1001; i++) {
			isPrime[i] = true;
		}
		
		// 에라토스테네스의 채
		for(int i=2; i*i<=1000; i++) {
			for(int j=i*i; j<=1000; j+=i) {
				isPrime[j] = false;
			}
		}
		
		int answer = 0;
		for(int n=0; n<N; n++) {
			if(isPrime[Integer.parseInt(tokens.nextToken())]) {
				answer ++;
			}
		}
		System.out.println(answer);
		
	}

	static String src =

			"4\r\n" + 
			"1 3 5 7";
}

 

 

후기

 

무슨 스킬을 쓰면 효율적이다라는건 알고있었지만 그 이름도 까먹었고 방식도 까먹었다. 

너무 오랜만에 알고리즘을 잡으니 뭔가 리마인드해야할 부분이 많은것 같다.

이제부터 부지런히 풀어보자!