[알고리즘] 백준 1929 : 소수 구하기 - S3

eternal moment·2023년 5월 8일
0

2023.04.21 풀이

import sys
input=sys.stdin.readline
import math

m,n=map(int, input().split())
arr=[True]*(n+1)
arr[1]=False

for i in range(2, int(math.sqrt(n))+1):
    if arr[i]==True:
        j=2
        while i*j<=n:
            arr[i*j]=False
            j+=1

for j in range(m,n+1):
    if arr[j]==True:
        print(j)

다른 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
d = [False, False] + [True] * (m-1)
primes, res = [], []
for i in range(2, m+1):
	if d[i]:
		for j in range(i*i, m+1, i):
			d[j] = False
for i in range(n, m+1):
	if d[i]:
		print(i)

check point

  • arr[1] 주의
    • 에라토스테네스의 체 : 여러 개의 수가 소수인지 아닌지 판별할때
      a. 2~n 까지 모든 자연수 나열
      b. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i 찾기
      c. 남은 수 중에서 i의 배수 모두 제거(i는 제거 x)
      d. 더 반복할 수 없을 때까지 b,c 반복
      -> 배수 지우기
import math

n=1000 #1000까지의 모든 수 소수판별
arr=[True for i in range(n+1)] # 모든 수가 소수(True)인 것으로 초기화(0과1은제외)


for i in range(2, int(math.sqrt(n)+1): #2~n의 제곱근까지 확인
	if arr[i]==True:   #i가 소수이면
    j=2        #i를 제외한 i의 모든 배수 지우기
    while i*j<=n:
    	arr[i*j]=False
        j+=1
        
# 모든 소수 출력
for i in range(2, n+1):
	if arr[i]==True:
    	print(i, end=" ")

0개의 댓글