[백준] 1929번 : 소수 구하기 with python3, go

11 Oct 2018

Reading time ~1 minute

문제: https://www.acmicpc.net/problem/1929

에라토스테네스의 체로 풀기

import sys
read = lambda : sys.stdin.readline().strip()

n, m = map(int, read().split())
check = [False]*(m+1)
check[0] = check[1] = True
i = 2
while i * i <= m:
    if check[i] == True:
      # 소수아니다
        i += 1
        continue
    j = i + i
    while j <= m:
        check[j] = True
        j += i
        # 배수들을 더하는 것이다.
    i += 1

for k in range(n, m+1):
    if check[k] == False:
        print(k)

package main

import "fmt"

func main() {
	var m, n int
	fmt.Scan(&m, &n)
	a := make([]bool, n+1)
	for i := 2; i <= n; i++ {
		if a[i] {
			continue
		}
		if i >= m {
			fmt.Println(i)
		}
		for j := i * 2; j <= n; j += i {
			a[j] = true
		}
	}
}