[백준] 1978 소수 찾기

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

1978번: 소수 찾기

 

소수를 찾는 문제는 프로그래머스에서 은근히 꽤 나왔던 것 같아서 여러 방법으로 해결해보려고 하고 있다. 그런데 정확성이나 효율성을 전반적으로 따져봤을 때 에라스토텔레스의 체를 이용해서 구하는 방법이 제일 좋아보여서 이 방법을 최대한 이용해보려고 한다.

 

---

문제 및 입출력

 

---

코드

import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        if(n<=1)
        {
            System.out.println(0);
            return;
        }
        
        // 최대값 1000으로 설정
        int cnt = 0;
        boolean[] arr = new boolean[1001];        
        arr[0] = false;
        arr[1] = false;
        
        // 에라스토텔레스의 체 구현
        for(int i=2; i<1001; i++)
        {
            arr[i] = true;
        }
        
        for(int i=2; i*i<1001; i++)
        {
            if(arr[i])
            {
                for(int j=i*i; j<1001; j+=i)
                {
                    arr[j] = false;
                }
            }        
        }
        
        // 입력받은 값들이 소수이면 +해서 결과 출력
        for(int i=0; i<n; i++)
        {
            if(arr[sc.nextInt()])
            {
                cnt++;
            }
        }
        
        System.out.println(cnt);
    }
}