[알고리즘] 백준 1929번 : 소수 구하기 (Koltin)

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

1. Scanner + sqrt

  
  fun main() = with(Scanner(System.`in`)) {

      val N = nextInt()
      val M = nextLine().trim().toInt()
      val check = BooleanArray(M + 1)

      for (i in check.indices) check[i] = true

      val sqrt = sqrt(M.toDouble()).toInt()
      for (i in 2..sqrt) {
          if (check[i]) {
              var j = i
              while (j * i <= M) {
                  check[i * j] = false
                  j++
              }
          }
      }
      for (i in N..M) {
          if (i == 1) continue
          if (check[i]) println(i)
      }
  }
  

 

2. BufferedReader + StringBuilder + split

  
  fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
      val sb = StringBuilder()
      val NM = readLine().split(" ")
      val N = NM[0].toInt()
      val M = NM[1].toInt()

      val prime = BooleanArray(M + 1)

      for (i in 2..M) {
          if (prime[i]) continue
          if (i >= N) sb.append(i).append("\n")

          var j = i + i
          while (j <= M) {
              prime[j] = true
              j += i
          }
      }
      println(sb)
  }
  

 

3. BufferedReader + StringBuilder + StringTokenizer

  
  fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
      val sb = StringBuilder()
      val st = StringTokenizer(readLine(), " ")
      val N = st.nextToken().toInt()
      val M = st.nextToken().toInt()

      val prime = BooleanArray(M + 1)

      for (i in 2..M) {
          if (prime[i]) continue
          if (i >= N) sb.append(i).append('\n')

          var j = i + i
          while (j <= M) {
              prime[j] = true
              j += i
          }
      }
      println(sb)
  }