[백준] 1978번 소수 찾기

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q1978.java

주어진 숫자들 중 소수의 개수를 출력하여라.

처음 생각

소수를 구할 수 있는 다양한 방법들이 있지만 에라토스테네스 체를 사용하는것이 가장 간단하면서 괜찮은 속력을 보장해주는것 같다. 특히, 이처럼 다양한 숫자들을 검사해야할 때는 매번 소수 판별을 하는 것보다 에라토스테네스 체를 이용해서 한 번에 구해놓는것이 좋다.

▶ 범위가 1000까지 이므로 1000이하의 모든 소수를 구해놓은 뒤, 주어진 숫자들중 소수의 개수를 세어 출력해주었다.

방안

1) Java 풀이

package baekjoon.q1000;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q1978 {
    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[1001];
        // 1은 소수가 아니다
        arr[1] = 1;
        // 에라토스테네스 체(미리 구해놓기)
        for(int i=2;i<=1000;i++){
            for(int j=2;i*j<=1000;j++)
                arr[i*j]=1;
        }
 
        int result = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()){
            int t = Integer.parseInt(st.nextToken());
            if(arr[t]==0) result++;
        }
        System.out.println(result);
    }
}
 

2) Python 풀이

n = int(input())
 
# 1000 이하 소수 미리 찾기
arr = [0 for i in range(1001)]
 
for i in range(2,1001):
    if arr[i]!=0:
        continue
    for j in range(2,1001):
        if i*j>1000:
            break
        arr[i*j]=1
result = 0
# 1은 소수가 아니다
arr[1] = 1
t = list(map(int,input().split()))
for i in range(n):
    if arr[t[i]]==0:
        result+=1
print(result)