[Go] 백준 1124번 언더 프라임 (소수가 약점인 것 같습니다.)

문제

https://www.acmicpc.net/problem/1124

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 언더프라임 개수를 출력한다.

---

문제 풀이

문제 해석 및 계획

A부터 B까지의 수가 2부터 증가하며 반복적으로 나누고 그 횟수를 확인하면 인수의 개수를 알 수 있고 인수의 개수가 1개라면 소수일 것이라고 생각하여 정답을 찾을 수 있을 것이라고 생각하였습니다.

나의 정답

1부터 B까지의 소수와 각 인수가 몇 개인지 확인하려고 하니 시간이 초과되었습니다.

고민한 끝에 이전에 문제에서 소수를 찾는 방법으로 '에라토스테네스의 체'라는 것이 생각났습니다.

정확하게 기억나진 않았지만 2부터 i를 곱하며 확인하는 방법이었던 것 같아 구현하여 각 수가 가진 인수를 구하였습니다.

인수를 구하고 나니 A부터 B까지 인수로 나누어지는 횟수를 확인하였고 그 횟수가 소수인지 확인하기 위하여 list의 값을 확인하였습니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var A, B int
	fmt.Fscan(reader, &A, &B)

	list := make(map[int][]int,B)
	for i:=2 ; 2*i<=B ; i++ {
		if len(list[i]) == 0 {
			for j:=1 ; i*j<=B ; j++{
				list[i*j] = append(list[i*j],i)
			}
		}
	}

	answer := 0
	for i:=A ; i<=B ; i++{
		cnt := 0
		nowNum := i
		for j:=0 ; j<len(list[i]); {
			if nowNum % list[i][j] != 0{
				j++
				
			}else {
				cnt++
				nowNum/=list[i][j]
			}
		}
		if len(list[cnt]) == 1 && cnt/list[cnt][0] == 1 {
			answer ++
		}
	}
	fmt.Fprint(writer, answer)
}

배운 정답

문제를 풀고 다른 사람들의 풀이를 구경하던 중 발견한 풀이를 보고 스스로 다시 작성한 코드입니다.

저는 list에 숫자를 인수분해하는 소수들이 저장되었고 아래의 정답은 인수의 개수를 저장하였습니다.

k는 i의 배수이기에 k가 가진 i의 개수만큼 증가시켰습니다. 두 번에 나누어하였던 작업을 3중 for문을 통하여 한번에 해결하는 코드가 깔끔해 보여 배워두었습니다.

ex)

i=2, k=12, 12/2 = 6, 6/2 = 3, 12에 2는 2번,

i=3, k=12, 12/3 = 4, 12에 3은 1번)

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var A, B int
	fmt.Fscan(reader, &A, &B)

	list := make([]int,B+1)
	for i:=2 ; 2*i<=B ; i++ {
		if list[i] == 0 {
			for j:=1 ; i*j<=B ; j++{
				k:= i*j
				for k%i == 0{
					list[i*j]++
					k/=i
				}
			}
		}
	}

	answer := 0
	for i:=A ; i<=B ; i++{
		if list[list[i]] == 1{
			answer++
		}
	}
	fmt.Fprint(writer, answer)
}

---

느낀 점

소수를 다루는 문제가 취약한 것 같습니다. 머릿속으로 코드를 돌려보아도 숫자가 커지면 소수가 맞는지 확인하는 과정도 쉽지 않아 다른 로직을 짜는 문제보다 항상 소수를 다루는 문제에서 헤매게 되는 것 같습니다.

이전에 배운 '에라토스테네스의 체'가 떠올라 스스로의 힘으로 해결할 수 있었고 이를 통하여 약점도 노력으로 극복할 수 있다는 것을 느꼈고 더욱 노력하여야겠다고 다짐하였습니다.