백준 1978번
https://www.acmicpc.net/problem/1978
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
첫번 째 삽입되는 숫자로 판단해야 할 숫자의 개수를 파악하고 변수loop
로 지정해주었다.
(변수의 개수 만큼 반복)
다음은 List
를 생성 후 변수들을 모두 삽입해줍니다.
(일반 Array 사용하셔도 괜찮습니다. 저는 List를 선호해서 사용했습니다.)
이제 판단할 숫자를 하나씩 꺼내서 소수인 숫자들만 세아려주면된다.
prime_Number
변수를 소수의 개수를 저장할 변수로 만들어 주고, 가장 먼저 1은 소수가 아니기때문에 예외로 생각해서 if문으로 continue
를 설정해 지나치도록 해주었다.
그리고 숫자가 소수인지를 판단할 때는 에라토스테네스의 체를 사용하도록 했다.
에라토스테네스의 체는 해당 숫자를 100이라고 가정했을 때, 100의 루트를 씌운 값 인 10까지만 배수를 찾으면 되는 소수를 찾을 때 아주 효율적인 방법이다.
sqrt
변수의 값이 10이 되는 것이다.
먼저 소수가 아닐 경우의 동작이다.
100을 기준으로 보면 sqrt
는 10(100의 루트값)이 되어,j
는 2부터 10까지 반복한다.
2일 경우에 2의 배수인지 검사하는 것이다. 여기서 2와 100을 나누면 나머지가 0이기 때문에 2의 배수에 해당되면서 소수가 아님을 의미하게 된다.
이런 경우는 굳이 3,4.. 뒤의 배수들을 검사 할 필요가 없기 때문에 한번이라도 나머지가 0이 되면 바로 break
로 List
에 있는 다음 숫자를 검사하도록 한다.
이번엔 소수일 경우의 동작을 살펴보자.
만약 소수인 17일 경우 temp
값이 17이 되고 sqrt
는 4가 된다.
이렇게되면 17이 2, 3, 4의 배수인지 반복해서 검사해서 나머지를 찾으면 된다.
j
가 2,3,4를 반복해서 17과 나누어서 나머지가 0인 경우가 있는지 검사한다 하지만 2, 3, 4의 배수가 아니기 때문에 반복문을 모두 마치게 되는데 이때 sqrt == j
의 조건에 부합하면 j
반복문을 모두 마쳤을 때 소수가 맞음을 알게되고 prime_Number
를 증가시켜 소수의 개수를 하나 증가시키게 된다.
이런식으로 반복해서 소수의 개수를 구할 수 있다.
백준 '소수 구하기' 문제를 푼지 2일도 채 안되서, 다시 소수 문제가 나왔다..
이제 소수라면 진절 머리가 날 정도다..
근데 이렇게 반복하면 정말 도움이 많이 된다는 걸 알기 때문에 마음을 다잡고 했는데, 이상하게 전에 소수 구하기 문제 보다 쉽다는 생각이 들었다.
확실히 '소수 구하기' 문제에서 고생한 보람이 있는지 에라토스테네스의 체를 활용해서 쉽게 해결할 수 있었다.
고마워요 에라토스테네스!
당신의 친절한 이웃
-에라토스테네스-
(스파이더맨 아님 기분탓임)
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; int loop = Integer.parseInt(br.readLine()); st = new StringTokenizer(br.readLine()); List<Integer> list = new ArrayList<>(); for(int i=0; i<loop; i++) { list.add(Integer.parseInt(st.nextToken())); } int prime_Number = 0; for(int i=0; i<loop; i++) { // 소수의 개수 int temp = list.get(i); // 1은 소수가 아니기 때문에 건너뜀. if(temp == 1) { continue; } else { int sqrt = (int) Math.sqrt(temp); // sqrt 1은 무조건 소수임(2와 3이 해당). if(sqrt == 1) { prime_Number++; } else { for(int j=2; j<=sqrt; j++) { if(temp % j == 0) { // 한번이라도 나머지가 0이 걸리는 게 있다면 소수가 아니기때문에 out break; } if(j == sqrt) { { // 소수임 prime_Number++; } } } } } System.out.println(prime_Number); } }