[백준 1929] 소수 구하기

 

1부터 1000000의 수 중에 2가 아닌 2의 배수, 3이 아닌 3의 배수, 5가 아닌 5의 배수를 제외한 나머지를 출력한다.

 

 

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int m = sc.nextInt();
        int n = sc.nextInt();
        int prime[] = new int[n+1];
        prime[1] = 0;
        for(int i=2; i<=n; i++)
            prime[i] = 1;
        
        for(int i=2; i<=n; i++) {
            for(int j=2; j<=n; j++) {
                if(i*j > n)
                    break;
                prime[i*j] = 0;
            }
        }
        
        for(int i=m; i<=n; i++) {
            if(prime[i] == 1)
                System.out.println(i);
        }
        
        sc.close();
}