17. 소수(에라토스테네스의 체)

소수 구하는 방법론에서는 에라토스테네스 체가 가장 빠르다. 이중 포문으로 돌려서 20만이 넘으면 time리미트가 뜬다. 

ch = new int [21] //배열은 0부터 시작이니까 

0,1은 소수의 대상이 아니므로 for문의 i가 2일 때부터로 한다. 

ch[i] == 0 이면 소수이므로 (2의 배수가 2, 4, 6, ...이라면 2는 2, 4, 6의 약수라는 의미인데 ch[i]가 체크가 안되고 0값 그대로 있다는 거는 2부터 i전까지의 숫자 중 i를 배수로 갖는 숫자가 없다는 걸 의미한다. 즉 i의 약수가 존재하지 않았다.)

카운팅하고 i의 배수들을 체크해야한다. (0 -> 1)

 

import java.util.Scanner;

public class Main {
    public int solution(int n) {
        int answer = 0;
        int[] ch = new int[n + 1]; //n+1로 해야 n번 index까지 생김
        for (int i = 2; i <= n; i++) {
            if(ch[i] == 0){
                answer ++;
                for (int j = i; j <= n; j=j+i) //i의 배수 찾기
                    ch[j]=1;
            }
        }
        return answer;
    }
   public static void main(String[] args){
       Main T = new Main();
       Scanner kb = new Scanner(System.in);
       int n=kb.nextInt();
       System.out.println(T.solution(n));

   }
}

i의 배수 찾는 과정에서 j = j+1 주의!

 

다른풀이

-boolean을 이용하여 true-> 소수가 아님

 import java.util.Scanner;

public class Main {
    public int solution(int n) {
        int answer = 0;
        boolean[] s = new boolean[n + 1];
        s[0] = true;
        s[1] = true;
        for (int i = 2; i <= n; i++) {
            if (s[i] == false) answer ++;
            for (int j = i*i; j <=n ; j+=i)
                s[j]=true;
        }
        return answer;
    }
   public static void main(String[] args){
       Main T = new Main();
       Scanner kb = new Scanner(System.in);
       int n=kb.nextInt();
       System.out.println(T.solution(n));

   }
}