티스토리 뷰

문제
 

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

풀이
package main

import (
	"bufio"
	"fmt"
	"os"
	"math"
	"sort"
)

func main() {
	var m, n int
	reader := bufio.NewReader(os.Stdin)
	fmt.Fscanln(reader, &m,&n)

	var primeNumber = make(map[int]bool, n-m+1)
	for i:=m; i<n+1; i++ {
		primeNumber[i] = true
	}
	if m == 1 {
		primeNumber[m] = false
	}

	for i:=m; i<n+1; i++ {
		var divisorCount int
		if primeNumber[i] {
			for j:=0; j<int(math.Sqrt(float64(i))); j++ {
				if i%(j+1) == 0 {
					divisorCount++
				}
				if divisorCount > 1 {
					primeNumber[i] = false
					// 에라토스테네스의 체
					for k:=1; k*i< n+1 ; k++ {
						primeNumber[k*i] = false
					}
					break
				}
			}
		}
	}

	var keys []int
	for i, v := range primeNumber {
		if v {
			keys = append(keys, i)
		}
	}

	sort.Ints(keys)

	for _, k := range keys {
		fmt.Println(k)
	}
}
728x90
댓글