[백준 1978] 소수 찾기

글에 개요

백준 알고리즘 1978번 "소수 찾기" 문제입니다. 에라토스테네스의 체 개념을 알면 쉽게 해결할 수 있습니다.

앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.

에라토스테네스의 체 (Sieve of Eratosthenes)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!!

에라토스테네스 체를 활용한 두 번째 문제이므로 참고할 만한 글을 통해 여러 문제를 풀어보시는 것을 추천드립니다.

이 후 이 문제를 통해 확장할 수 있는 문제가 많기 때문에 더더욱 익히셨으면 좋겠습니다. 

[백준 1978] 소수 찾기: https://www.acmicpc.net/problem/1978

참고할 글

1. http://brenden.tistory.com/48 ([알고리즘] 에라토스테네스의 체 정리글)
2. http://brenden.tistory.com/49 ([백준 2960] 에라토스테네스의 체)

핵심 내용

1. 에라토스테네스의 체 개념을 묻는 문제이다.
2. 1001까지의 모든 소수를 판단할 수 있는 isPrime 배열에 담아줍니다.
3. 해당 Index에 소수인지 파악하여 총 갯수를 세줍니다.

해결 방법

1. 소수인지 아닌지 여부를 파악하기 위한 isPrime 배열의 초기화를 진행해 줍니다.
2. line 15, 16 line을 통해 소수 여부를 갱신해 줍니다.

해결한 코드

	import java.util.Scanner;
	public class Main {
	public static final int MAX = 1001;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	boolean[] isPrime = new boolean[MAX];
	for(int i = 2; i < MAX; i++) {
	isPrime[i] = true;
	}
	for(int i = 2; i < MAX; i++) {
	for(int j = 2 * i; j < MAX; j += i) {
	if(!isPrime[j]) continue;
	isPrime[j] = false;
	}
	}
	int n = sc.nextInt();
	int cnt = 0;
	for(int i = 0; i < n; i++) {
	int x = sc.nextInt();
	if(isPrime[x])
	++cnt;
	}
	System.out.println(cnt);
	}
	}

view raw B_1978.java hosted with ❤ by GitHub

백준 참고 내용

소수 찾기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	15415	7573	6328	51.297%

문제

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

입력

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

출력

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

예제 입력 1 

4
1 3 5 7

예제 출력 1 

3