[SWEA][JAVA]D3 : 100만 이하의 모든 소수

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV_6mRsasV8DFAWS&categoryId=AV_6mRsasV8DFAWS&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=30&pageIndex=5 

SW Expert Academy

 

 

---

 

범위가 넓을때 소수 구하기 : 에라토스테네스의 체

 

배열을 동적배열해주어 모든값을 0으로 세팅하고

첫 소수 2부터 시작하여, 해당 인덱스의 값이 0이면 소수, 그리고 해당 값의 배수들을 모두 1로 바꾼다.

 

 

import java.util.Scanner;
class Solution{
    public static void main(String args[]) throws Exception{
        Scanner kb=new Scanner(System.in);
        int[] arr=new int[1000000+1];
        for(int i=2; i<arr.length; i++){
            if(arr[i]==0){
                System.out.print(i+" ");
                for(int j=i; j<arr.length; j+=i)
                    arr[j]=1;
            }
        }
    }
}