[백준 / Go] 1124번: 언더프라임

문제

1124번: 언더프라임

자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.

어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.

두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.

입력

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

출력

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

---

문제 이해하기

 두 정수 A와 B 사이의 언더프라임, 소인수의 개수가 소수인 수의 개수를 구하는 문제입니다. 우선 소수인지 여부를 판별하기 위해 에라토스테네스의 체를 사용한 소수 판별이 필요합니다. 그리고 A와 B 사이의 각각의 수의 소인수를 구해야 하는데, 이를 매번 구하려면 시간 초과가 발생할 수 있습니다. 따라서 메모이제이션을 통해 각 정수가 가진 소인수의 최솟값을 저장하고 이를 활용해 소인수의 개수의 합을 구합니다. 마지막으로, 소인수의 개수의 합이 소수인지를 판별하여 언더프라임의 개수를 구합니다.

---

코드

package main

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

var (
	scanner      = bufio.NewScanner(os.Stdin)
	writer       = bufio.NewWriter(os.Stdout)
	A, B         int
	isPrime      [100001]bool
	minFactor    [100001]int
	primeFactors [100001]int
)

func main() {
	defer writer.Flush()
	scanner.Split(bufio.ScanWords)

	Setup()
	Solve()
}

func Setup() {
	A, B = scanInt(), scanInt()

	for i := 2; i <= B; i++ {
		isPrime[i] = true
	}

	for i := 2; i <= B; i++ {
		if isPrime[i] {
			minFactor[i] = i
			for j := i * i; j <= B; j += i {
				isPrime[j] = false
				minFactor[j] = i
			}
		}
	}

	for i := 2; i <= B; i++ {
		primeFactors[i] = primeFactors[i/minFactor[i]] + 1
	}
}

func Solve() {
	count := 0
	for i := A; i <= B; i++ {
		if isPrime[primeFactors[i]] {
			count++
		}
	}

	fmt.Fprintln(writer, count)
}

func scanString() string {
	scanner.Scan()
	return scanner.Text()
}

func mustParseInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func scanInt() int {
	return mustParseInt(scanString())
}

메모리: 2512 KB

시간: 8 ms

분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!