[알고리즘/백준] 1978 소수 찾기(자바, 에라토스테네스의 체)

[알고리즘/백준] 1978 소수 찾기(자바, 에라토스테네스의 체)

문제

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

풀이 코드

에라토스테네스의 체 알고리즘을 사용하여 풀이

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] arr = new int[n]; int max = Integer.MIN_VALUE; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); max = Math.max(max, arr[i]); } //배열의 인덱스는 수, 값이 true 이면 소수가 아니다. boolean[] isNotPrimes = new boolean[max+1]; //1은 소수가 아니다. isNotPrimes[1] = true; //에라테네스 체 알고리즘 사용하여 1 ~ max 범위의 소수 판별 for (int i = 2; i <= max; i++) { if (!isNotPrimes[i]) { for (int j = i * 2; j <= max; j += i) { isNotPrimes[j] = true; } } } int count = 0; //소수 개수 for (int num : arr) { if (!isNotPrimes[num]) { count++; } } System.out.println(count); } }

에라토스테네스의 체 알고리즘은 소수를 판별할 때 자주 사용되는 알고리즘이다.

해당 알고리즘에 대해 알고싶다면 아래 링크의 게시물이 도움이 될 것이다.

https://developer-hm.tistory.com/64

728x90

from http://developer-hm.tistory.com/165 by ccl(A) rewrite - 2021-09-24 19:01:38