[1929]N이상M이하 소수구하기

 

문제 설명

M이상 N이하 소수를 구하면 된다.

 

 

소수란 1과 자기자신 만을 약수를 가지는 수를 말한다.

 

우리는 어떤 수의 약수를 구할 때 어떻게 하는가?

N의 약수를 구해보자

1~N까지 반복문을 돌려, N과 %연산을 해보면 된다.

조금더 빠르게 구해보자

1~sqrt(N)까지 반복문을 돌려, N과 %연산을 해보면 된다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static boolean[] TF;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        StringTokenizer st = new StringTokenizer(br.readLine());


        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        //이까지 입력

        StringBuilder sb = new StringBuilder();
        
        //출력을위한 StringBuilder선언

        TF = new boolean[N+1];	//소수인지 판단할 TF배열 선언
        prime();	//1~N까지의 수에 대해 소수를 판단.

        for(int k=M;k<=N;k++){
            if(!TF[k])
                sb.append(k).append('\n');
        }
        //M에서 N까지 소수 append
        
        System.out.println(sb);
        //sb출력
    }

    public static void prime(){
        TF[0] = true;
        TF[1] = true;
        //0과 1은 소수가 아니기 때문에 true로 

        for(int i=0;i*i<=TF.length;i++){	//N까지의 수에 대해서 반복문진행
            if(TF[i])		//이미 소수가 아니면
                continue;	//통과
            for(int j=i*i;j< TF.length;j+=i)	//그렇지 않으면 그 수(i)의 배수에 대해 접근하는 반복문
                TF[j]=true;		//그 배수들을 소수로 만들어준다.
        }
    }
}

 

1. 먼저 이 개념을 이해하기 전에 모든 수는 소수들의 곱으로 표현된다는 사실을 알 필요가 있다.

(예를들어 34의 경우 2x17 이다, 2는 소수이고 17도 소수이다.)

2. 그래서 에라토스테네스의 체 개념은 1~N 까지 수를 증가시키다가, 소수를 찾고 소수를 찾은 즉시 그 소수들의 배수를 제외시킨다. 그러면  남는수는 결국 소수일 것이다. 라는 개념이다.