소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

그냥 n제곱으로 돌리면 시간초과

sqrt(n)으로 제곱근(제곱근까지 해도 그냥 소수와 결과가 같다)을 돌리거나

에라토스테네스의 체

n까지 입력받으면 인덱스를 각 자릿수로 초기화

만난 수가 0이 아니면 그 수의 배수들을 전부 0으로 바꾸는 연산을 n이 될때가지 수행

남아있는 수는 소수

에라토스테네스의 체로 구했다

 

import java.util.*;

public class Solution {
    public int solution(int n) {
        int answer = 0;
        
        int[] arr = new int[n+1];
        //배열 초기화
        for (int i =2; i <= n; i++) arr[i] = i;

        for (int i = 2; i <= Math.sqrt(n); i++){
            if (arr[i] == 0) continue;
            for (int j = 2*i; j <= n; j+=i) {
                arr[j] = 0;
            }
        }

        for (int x : arr) if (x != 0) answer++;

        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.print(T.solution(n));
    }
}