본문 바로가기
👩‍💻TIL/백준 알고리즘

[백준 알고리즘] 문제 2581 - 소수 구하기

by devuna 2020. 1. 21.
728x90

백준 알고리즘 문제 2581 - 소수 구하기

 

 

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

 

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

두 자연수 사이의 소수의 갯수를 정확하게 알지 못하기 때문에,

  1. 생성시에 크기를 지정해주지 않아도 되는 ArrayList를 사용하였으며

  2. 이중 For문을 이용하여 소수를 판별하여 ArrayList에 담아 최소값과 합계를 구하였다.

소스코드

public static void main(String[] args) {

	Scanner sc = new Scanner(System.in); //스캐너로 두 개의 정수를 입력받는다.
	System.out.print("입력 1:");
	
    int M = sc.nextInt();
	System.out.print("입력 2:");

	int N = sc.nextInt();
	int sum = 0; //합계를 담아줄 변수 sum 선언

	ArrayList alist = new ArrayList(); //판별한 소수를 담아줄 ArrayList 선

	if(M>N) { //둘 중 작은 수를 M 큰수를 N에 넣기 위해 IF문 설정

	int tmp = M;
	M=N;
	N=tmp;
}

for (int i = M; i <= N; i++) { //소수 판별을 위한 이중 for	
	int count = 0;
	for (int j = 2; j < i; j++) {
		if (i % j == 0) {
			count += 1;
		}
	}
	if (count == 0) {
		alist.add(i);
	}
}
for (int i = 0; i < alist.size(); i++) {
	sum += (int) alist.get(i);
}
    
Collections.sort(alist); // 작은 값을 제일 앞으로 정렬
System.out.println("최소값 : " + alist.get(0)); // 0번째 값 =최소값 출력
System.out.println("합 계 : " + sum);
}
728x90

댓글