[백준] 소수 찾기 (BufferedReader, StringTokenizer, 1978번)

 

▶ BufferedReader, StringTokenizer를 활용한 간단한 문제가 있어 정리해보고자 합니다.

 
 

문제설명

입력 & 출력

나의 풀이

빠른 입력을 위해 BufferedReader 클래스를 사용했습니다.
 
StringTokenizer 클래스를 사용하여 공백을 기준으로 나눠주고, int형으로 캐스팅한 후 num 변수에 저장해 줍니다.
 
그리고 소수를 찾기 위한 함수 isPrime()을 만들어줍니다.
 

소수란❓  1과 자신 외에는 다른 약수를 가지지 않는 1보다 큰 자연수입니다.

즉 소수는 두 개의 고유한 약수를 갖는 수입니다. 예를 들어 2, 3, 5, 7, 11 등이 소수이며 소수는 2를 제외한 홀수뿐입니다.

 
위 같은 소수의 특징이 있기 때문에 isPrime() 함수에서 인자로 받은 n이 1보다 작거나 같으면 소수가 아니고, 2는 유일한 짝수 소수입니다. 그리고 25번째 줄에서 짝수는 소수가 아니다는 조건을 넣어줍니다.
 
이제 3 이상의 수는 반복문을 사용해야 합니다. 여기서 2씩 증가하는 이유는 홀수를 걸러야 되기 때문입니다.
 
만약에 2가 들어오면 2는 유일한 짝수인 소수이기 때문에 true가 반환되고, 5면 반복문에 들어가 5 % 3!= 0 ➡ true , 5 % 4!= 0 ➡ true 가 반환됩니다.
 
반환된 isPrime()가 true면 소수이기 때문에 cnt를 증가시켜 줍니다.
 
위 코드에서 Math.sqrt() 제곱근 함수를 사용하는 이유는 시간복잡도 때문인데 제곱근함수를 사용하지 않으면 검사 범위가 √n에서 n으로 확장됩니다.
 
제곱근을 사용하는 경우

• 검사범위 : 3부터 √n까지
• 시간 복잡도 : O(√n)

제곱근을 사용하지 않는 경우

• 검사범위 : 3부터 n까지
• 시간 복잡도 : O(n)

---

• 예제 1) n이 29인경우:
• √29 = 5.3851648071345
  
  • 제곱근 함수를 사용하면 1,2,3,5 중 3과 5만 검사합니다.
  • 제곱근 함수를 사용하지 않으면 3,5,7,9,11,13,15,17,19,21,23,25,27까지 모두 검사합니다.

• 예제 2)n이 36인경우:
• √36 = 6
  • 36의 약수는 1,2,3,4,6,9,12,18,36입니다.
  • 이 약수들 중 6 이하의 약수는 1,2,3,4,6입니다. 나머지 약수들은 1,2,3,4,6의 배수입니다.
  • 제곱근 함수를 사용하면 1,2,3,4,6만 검사합니다.
  • 제곱근 함수를 사용하지 않으면  1,2,3,4,6,9,12,18,36까지 모두 검사합니다.

즉 n이 커지면 커질수록 소수인지 판별하기 위해 더 많은 검사를 해야 합니다.
 
 
 

참고 ❗

[JAVA] 입출력, BufferedReader, StringTokenizer