자연수 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을 출력한다.
60
100
620
61
64
65
-1
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
int cnt = 0;//소수 갯수
int sum=0; //소수 합
int min=0;//소수 최솟값
for(int i =M; i<=N; i++) { //M~N의 범위로 반복문
int count = 0;
for (int j = 2; j <=i; j++) {//소수 찾는 반복문
if (i % j == 0)
count++;
}
if (count == 1) {//count가 1이면 소수로 보고 작동
cnt++;
sum = sum + i;
if(cnt==1) //소수 갯수가 1개일때 최소값을 저장하기위한 if문
min=i;
}
}
if(cnt ==0){ //소수가 없다면 작동
System.out.println("-1");
}
else{
System.out.println(sum);
System.out.println(min);
}
}
}
문제 풀때 for문, if문을 써서 시간복잡도를 줄이기엔 한계가 있다.
다른 사람들 코드 보면서 다양하게 쓰면서 줄여보자