D+8 백준 2581 소수

백준 2581 소수 - 실버 5

이것도 1978번이랑 똑같이 에라토스~의 채로 풀면된다.

아이디어는 하기와 같다.

1) 1~10001크기의 배열을 만들고 1로 값을 채운다.

2) for문으로 배수를 돌아가면서 배수이면 0값을 넣어준다.

10000까지돌았을때, 배열의 값이 1인 값들은 소수 0인값들은 소수가 아닌수로 남게된다.

M~N까지 의 방에 값들이 1의인 배열방의 순서들을 더한다. ex) arr[67]은 숫자 67을 나타낸다.

https://www.acmicpc.net/problem/2581 

2581번: 소수

 

import java.io.*;
import java.util.*;

public class Main {
   
    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());
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        
        int []arr = new int[10001];
        for(int i=2; i<arr.length; i++){
            arr[i] = 1; 
        }
        
        for(int i=2; i<arr.length-1; i++){
            if(arr[i]==0){continue;}
            for(int j=i+1; j<arr.length; j++){
                if(j%i==0){
                    arr[j] = 0; //배수이면 0 넣음. 
                }
            }
        }
        int sum=0; int min = 10000;
        for(int i=m ; i<=n; i++){
            if(arr[i]==1){ // 이면 소수
                sum += i;
                if(i<min){
                    min = i;
                }
            }
        }
        if(sum==0){
            System.out.println(-1);
            return;
        }
        System.out.println(sum);
        System.out.println(min);
    
    
    }// main method end
}//class end