에라토스테네스 체

import java.util.*;

class Main {
    public int solution(int size) {
        int count = 0;
        int[] numArray = new int[size+1]; // n까지 입력받을 배열 0~n임으로 n-0+1이 배열크기

        for(int i = 2; i <= size; i++){ // 0과1은 소수에 영향을 주지않음 2부터 시작
            if (numArray[i] == 0){// 해당 배열의 값이 0이면 해당 숫자는 약수를 가지지 않는다는것
                count++;
                for(int j = i ; j <= size; j += i){//배열안에 i의 배수를 제거함 
                    numArray[j] = 1;
                }
            }
        }
        return count;
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner scanner = new Scanner(System.in);
        int s = scanner.nextInt();
        System.out.println(T.solution(s));

    }

}

j < size는 제곱근으로 대체할 수 있다. 

 

원리는 2부터 시작해서 자기 자신의 배수를 지우는 식으로 진행한다.