[백준] 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을 출력한다.

 

해결방법 > 

n까지의 소수를 찾기위해서 n^(1/2)까지만 탐색

 

C++

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

int main(){
    int m, n;
    int min = 0, sum = 0;
    cin.tie(0);

    cin >> m >> n;
    if(m == 1)
        m = 2;
    for(int i = m; i <= n; i++){
        bool c = true;
        for(int j = 2; j <= sqrt(i); j++){
            if(i % j == 0){
                c = false;
                break;
            }
        }
        if(c == true){
            if(min == 0)
                min = i;
            sum += i;
        }
    }

    if(min == 0)
        cout << -1 << '\n';
    else
        cout << sum << '\n' << min << '\n';
}

 

JAVA

package baekjoon;

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int start = sc.nextInt();
		int end = sc.nextInt();
		int sum = 0;
		int min = 0;
		String s;
		
		for(int i = start; i <= end; i++) {
			boolean prime = true;
			
			if(i == 1)
				continue;
			
			for(int j = 2; j <= Math.sqrt(i); j++) {
				if(i % j == 0) {
					prime = false;
					break;
				}
			}
			
			if(prime == true) {
				sum += i;
				
				if(min == 0) {
					min = i;
				}
			}
		}
		if(min == 0)
			s = -1 + "\n";
		else
			s = sum + "\n" + min;
		System.out.print(s);
	}
}

 

문제링크 >

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