자바 기초 문제, 소수 구하기 (백준 알고리즘 2581번 문제)

 

 

 

문제 2581번 소수

 범위 n, m를 입력받고, 범위내의 소수들의 합과 최소값을 출력해준다.

 

 

 

 

 

 

입력조건

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

 M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

 

 

출력

 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

 

풀이과정

1. 알고리즘을 풀어본다.

 

  1) n, m을 입력 받는다.

  2) 소수를 판별한다.

  3) 범위 내 소수가 없으면 -1을 출력하고 있으면 합계와 최소값을 출력한다.  

 

n, m을 입력 

   for(n부터 m까지 소수판별 테스트를 한다) 

for (1부터 n까지의 숫자)
      if(1부터 n-1 까지의 숫자를 n에 나눴을때 나눠지면 소수가 아니므로 break로 빠져 나간다)
      if(한번도 나누어 지지않고 n까지 오면 이것은 소수이므로 sum에 합계를 더하고 최소값으로 입력한다.)

 if (소수가 한번도 나오지않은 sum = 0 상태이면) -1 출력하고

 else 아니면 합계와 최소값 출력.

 

 

 

2. 식으로 구현한다.

import java.util.Scanner;

public class Main {

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

int n = sc.nextInt();
int m = sc.nextInt();
int sum = 0;
int min = 0;

for (int i = m; i >= n; i--) {
for (int j = 2; j < i; j++) { 
if (i % j == 0) {
break;
}
if (i == j+1) {
sum += i;
min = i;
}
}

}
if(sum == 0) {
System.out.println(-1);
}else {
System.out.println(sum);
System.out.println(min);
}
}
}

3. 결과 : 틀렸습니다.

예제는 풀어지나, 2는 현재 소스 중 for문에 진입할 수 가 없다.

for문 조건을 수정함으로서 if 조건도 수정.

4. 성공 코드

import java.util.Scanner;

public class Main {

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

int n = sc.nextInt();
int m = sc.nextInt();
int sum = 0;
int min = 0;

for (int i = m; i >= n; i--) {
for (int j = 2; j <= i; j++) { 
if (i % j == 0 && i!=j) {
break;
}
if (i == j+1 || i == 2) {
sum += i;
min = i;
}
}

}
if(sum == 0) {
System.out.println(-1);
}else {
System.out.println(sum);
System.out.println(min);
}
}
}

범위에 2가 포함 될 경우를 예외적으로 넣었더니. 식이 지저분하다 ㅠㅠ

깔끔한 방법이 있을텐데..

문제 출처

 

- Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 중등부 1번

- 문제 url : https://www.acmicpc.net/problem/2581