소수판별2

문제

자연수n,m이 주어질 때, n부터m까지 존재하는 소수를 모두 출력하는 프로그램을 작성하여라. 여기서 소수란, 약수가 1과 자기자신밖에 존재하지 않는 수를 말한다.

 

입력

첫째 줄에 자연수 n, m이 주어진다. (1≤n,m≤20,000)

출력

첫째 줄에 n부터m까지 존재하는 소수를 모두 출력한다.

 

 

 

이 문제의 포인트는 

2(소수)부터 해서 4,6,8,10,12,14,16,18,20... 2의 배수(즉,소수가 아닌 것들을 체크)

3(소수)부터 해서 6,9,12,15,18,21,24... 3의 배수(즉,소수가 아닌 것들을 체크)

...

즉, 아래 부분이 이 문제의 핵심.

 for(int i=2;i<MAX/2;i++)
            for(int j=i+i;j<MAX;j=j+i)
                isPrime[j]=false;
           

 

 

import java.util.Scanner;

public class Main
{
    public static int MAX = 20001;
    public static int[] arr = new int[MAX];
    public static boolean[] isPrime = new boolean[MAX];

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        initIsPrime();

        calculateWhetherNumberIsPrime();
//        printIsPrime();

        int start = scan.nextInt();
        int end = scan.nextInt();

        printAnswer(start,end);


        scan.close();
    }

    private static void printIsPrime()
    {
        for(int i=0;i<1000;i++)
        {
            System.out.print(isPrime[i]+" ");
        }
        System.out.println();
    }

    private static void printAnswer(int start,int end)
    {
        for(int i=start;i<=end;i++)
        {
            if(isPrime[i])
            {
                System.out.print(i+" ");
            }
        }
        System.out.println();
    }


    /**
     * 소수인지 아닌지 판별
     * TIME : o(N * logN)
     */
    private static void calculateWhetherNumberIsPrime()
    {
        for(int i=2;i<MAX/2;i++)
        {
            for(int j=i+i;j<MAX;j=j+i)
            {
                isPrime[j]=false;
            }
        }
    }

    /**
     * init isPrime Array
     * TIME : O(N)
     */
    private static void initIsPrime()
    {
        int len = isPrime.length;
        for(int i=0;i<len;i++)
        {
            isPrime[i]=true;
        }
        // 1 is not a prime number.
        isPrime[0]=false;
        isPrime[1]=false;
    }
}