백준 1929번 - 소수 구하기

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하면 된다.

 

public class Main{
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int m = Integer.valueOf(input[0]);
        int n = Integer.valueOf(input[1]);

        boolean[] isPrime = new boolean[n + 1];
        isPrime[0]=isPrime[1]=true;

        for (int i = 2; i <= n; i++) {
           if(isPrime[i])continue;
           for(int j = i*2 ;j<=n;j+=i)isPrime[j]=true;
        }

        for(int i=m;i<=n;i++)
        {
            if(!isPrime[i])System.out.println(i);
        }
    }
    
}

 

-에라토스테네스의 체 (O(nloglogn))

 

2~ N까지 범위 안에 포함되는 모든 소수를 구하는 방법이다.

 

- 2부터 N까지 수 중에 가장 작은 수를 택한다 (소수) -> 가장 작은수의 배수를 모두 지운다.

 

boolean[] isNPrime = new boolean[M+1]; //isNotPrime -> 소수면 false 짝수면 true
int[] primeNumber = new primeNumber[M]; // 소수 저장
int index =0;
isNPrime[0] = isNPrime[1] = true; // 0과 1은 소수가 아니다.

//소수들 저장하고 싶을 때
for(int i=2; i<=M; i++){
    if(isNPrime[i] == false){
      primeNumber[index++] = i;
      for(int j= i+i ; j<=M; j+=i){
      isNPrime[j] = true;
      }
    }
}

//소수 index에 true false값 저장한 배열만 만들고 싶을 때
for(int i=2; i*i<=M; i++){  // i의 배수는 모두 지워짐 i*i가 M을 넘어서면 검사할 필요없다.
	if(isNPrime[i])continue; 
    for(int j= i+i ; j<=M; j+=i){ 
      isNPrime[j] = true;
      }
}

소수숫자를 저장하고 싶으면, i <= M의 조건식으로 i++하면서 해야겠지만, 그런게 아니라면, 

i*i<= M의 (루트M 소수찾기 검사식)을 넣어도 된다. 왜냐면, 가령 M이 110이라고 해보자.

2의 모든 배수를 지우고나면, 3은 3*2가 이미 지워졌음으로 3*3부터 검사하면되고, 4는 4*4 ---> 10*10부터 검사하면된다 

그 전의 값들은 이미 그 밑의 수의 배수로 지워졌기 때문이다. 따라서 M이 110이면, 10*10까지만 검사하면되지 11은 어차피 11*11부터 검사할텐데 이는 121이라 어차피 M의 범위를 넘어가므로 검사할 필요가 없다.