BOJ 2581. 소수

[hojongs]

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

Impl

from sys import stdin

m = int(stdin.readline())
n = int(stdin.readline())

is_primes = [True] * (n+1)
is_primes[1] = False
is_prime_idx = 2

while is_prime_idx**2 <= n:
    is_prime_i = is_prime_idx+1
    while is_prime_i <= n:
        if is_prime_i % is_prime_idx == 0:
            is_primes[is_prime_i] = False
        is_prime_i += 1

    next_is_prime_idx = is_prime_idx+1
    while not is_primes[next_is_prime_idx]:
        next_is_prime_idx += 1
    is_prime_idx = next_is_prime_idx

primes = []
for i in range(m, n+1):
    if is_primes[i]:
        primes.append(i)

if len(primes) == 0:
    print(-1)
else:
    print(sum(primes))
    print(min(primes))

Explanation

에라토스테네스의 체

32

Improvement

https://mail-study.tistory.com/4 prime을 매 loop마다 찾을 필요가 없음 is_primes를 순회하며 prime을 발견할 때마다 loop를 돌면 됨 is_prime_i이 1씩 증가하는 대신, is_prime_i*j (j >= 2)를 하는 게 더 빠름

Retrospective

impl plan을 먼저 정리하지 않는다 (귀찮아서) 그래서 구현이 최적이 아니거나, 구현 도중에 최적으로 변경하기 어렵다 나중에 다시 풀어보자

[hojongs]

Impl (Go)

package main

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

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

    var candidates [1000001]bool
    for i := 0; i <= n; i++ {
        candidates[i] = true
    }
    candidates[0] = false
    candidates[1] = false
    i := 2
    for i*i <= n {
        if candidates[i] {
            ii := i * i
            for ii <= n {
                candidates[ii] = false
                ii += i
            }
        }
        i += 1
    }
    min := -1
    for i := m; i <= n; i++ {
        if candidates[i] {
            min = i
            break
        }
    }
    if min == -1 {
        fmt.Println(-1)
    } else {
        sum := 0
        for i := m; i <= n; i++ {
            if candidates[i] {
                sum += i
            }
        }
        fmt.Println(sum)
        fmt.Println(min)
    }
}