실력키우기 소수(JAVA)

1740 : 소수

제한시간: 1ms    메모리제한: 64MB
해결횟수: 963회    시도횟수: 2956회   

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최소값을 찾는 프로그램을 작성하시오.

 

예를 들어 M=60, N=100이 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최소값은 61이 된다.

 

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.
M과 N은 10,000이하의 자연수이며, M은 N보다 같거나 작다.

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최소값을 출력한다.
단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

[Copy] 60 100

[Copy] 620 61

?

1. /**************************************************************
2.     Problem: 1740
3.     User: a132034
4.     Language: Java
5.     Result: Success
6.     Time:197 ms
7.     Memory:11324 kb
8. ****************************************************************/
9.  
10.  
11. import java.util.Scanner;
12.  
13. public class Main
14. {
15.     public static void main(String[] args) {
16.         final int UNDEFINE = 0;
17.         final int PRIME = 1;
18.         final int NOT = 2;
19.          
20.         Scanner sc = new Scanner(System.in);
21.         int min = sc.nextInt();
22.         int max = sc.nextInt();
23.  
24.         int sum = 0 ;
25.         int minPrime = 0;
26.         boolean minFlg = true;
27.          
28.         int[] arr = new int[max+1];
29.         arr[1] = NOT;
30.         for(int i = 2; i <= max; ++i)
31.         {
32.             boolean isPrime = true;
33.             if(arr[i] == UNDEFINE)
34.             {
35.                 for(int j = 2; j < i; ++j)
36.                     if(i % j == 0)
37.                         isPrime = false;
38.                  
39.                 if(isPrime)
40.                     arr[i] = PRIME;
41.                  
42.                 for(int j = 2*i; j <= max; j = j+i)
43.                     arr[j] = NOT;
44.             }
45.         }
46.          
47.          
48.         for(int i = min; i <= max; ++i)
49.         {
50.             if(arr[i] == PRIME)
51.             {
52.                 sum+=i;
53.                 if(minFlg)
54.                 {
55.                     minPrime = i;
56.                     minFlg = false;
57.                 }
58.             }
59.         }
60.          
61.         if(sum != 0)
62.         {
63.             System.out.println(sum);
64.             System.out.println(minPrime);
65.         }
66.         else
67.             System.out.println(-1);
68.     }
69. }

어렵지 않게 풀었던 것 같다. 

일단 소수를 구하는 공식은 1과 자기 자신을 제외한 수로 나누어 떨어지면 안되기 때문에 단순하게 2부터 자기 자신의 전 까지 나누어보며 체크했다. 

시간을 줄이기 위해 값을 체크한 후, 값의 배수가 되는 값들을 모두 계산없이 소수가 아닌 것으로 판단해 주었다. 

방금 체크한 값의 배수라는 것은 체크한 값으로 나누어 떨어진다는 것. 

ex) 2가 소수이건 아니건 4, 6, 8, 10.... 2*x 는 모두 2로 나누어 떨어지기 때문에 소수가 아님. 

그외에는 크게 어려운 점은 없었다.