[BOJ/Step9] 2581 : 소수 (JAVA)

www.acmicpc.net/problem/2581

2581번: 소수

---

문제

자연수 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을 출력한다.

 

예제 입력 1

60

100

 

예제 출력 1

620

61

 

예제 입력 2

64

65

 

예제 출력 2

-1

---

풀이

1. M과 N이 10000이하의 자연수이므로 1~10000 사이의 소수를 미리 계산하여 배열에 넣어둔다.

   1-1. 소수는 1과 자기 자신으로만 나눠지는 수이므로, 2, 3, 5, …… 순이다.

   1-2. 2와 3부터 배열 prime[] 에 넣어두고

   1-3. 4~10000 의 수가 해당 prime의 수로 나누어지는지 확인하여 나누어지지 않는 수만 prime에 추가한다.

2. 최솟값을 저장할 min과 총 합을 저장할 total을 0으로 초기화한다.

3. 주어지는 m과 n 사이의 수가 prime에 존재하는지 확인하여 존재할 경우 min이 0일 때만 해당 수를 min에 저장하고 total에 더한다. ( 최솟값을 저장해야 하기 때문에 min에 이미 값이 있을 경우엔 최솟값이 아님 )

4. min이 0 이면 m과 n 사이에 소수가 존재하지 않았다는 뜻이므로 -1을, 그 이외엔 total과 min을 출력한다.

 

java

닫기 줄바꿈

import java.util.Scanner;

public class B2581 {

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

‌‌int prime[] = new int[1300];
‌‌int primeIdx = 1;
‌‌prime[0] = 2;
‌‌prime[1] = 3;
‌‌
‌‌Loop1 :
‌‌for(int i = 4; i <= 10000; i++) {
‌‌‌for(int j = 0; j < primeIdx; j++) {
‌‌‌‌if(i % prime[j] == 0) {
‌‌‌‌‌continue Loop1;
‌‌‌‌} else {
‌‌‌‌‌
‌‌‌‌}
‌‌‌}
‌‌‌prime[++primeIdx] = i;
‌‌}
‌‌
‌‌int m = sc.nextInt();
‌‌int n = sc.nextInt();
‌‌int min = 0;
‌‌int total = 0;
‌‌
‌‌for(int i = m; i <= n; i++) {
‌‌‌for(int j = 0; j <= primeIdx; j++) {
‌‌‌‌if(prime[j] == i) {
‌‌‌‌‌min = min == 0 ? prime[j] : min;
‌‌‌‌‌total += prime[j];
‌‌‌‌}
‌‌‌}
‌‌}
‌‌
‌‌if(min == 0) {
‌‌‌System.out.println("-1");
‌‌} else {
‌‌‌System.out.println(total);
‌‌‌System.out.println(min);
‌‌}
‌}
}