[Algorithm] 소수관련문제들

손시연·2022년 4월 4일

백준 파이썬

algorithm

목록 보기

2/18

에라토스테네스의 체

소수찾기 알고리즘

2부터 N까지의 모든 정수를 적는다. (True 값을 가짐)
아직 지우지 않는 수 중 가장 작은 수를 찾는다. 이것을 p 라고 하고, 이 수는 소수이다.
p를 지우고, 아직 지우지 않은 p의 배수를 크기 순서대로 지운다. (False 값을 가짐)
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

[예]
1. 2를 남겨두고, 2의 배수를 모두 지움
2. 2를 제외한 가장 작은 수인 3을 남겨두고, 3의 배수를 모두 지움
3. 다음 작은 수는 5이고 이 과정을 n까지 계속 반복하면 소수만 남는다.

def eratos(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    nums = [True] * (n+1)
    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m):
        if nums[i] == True:  # i가 소수인 경우
            for j in range(i+i, n+1, i):  # i이후 i의 배수들을 False 판정
                nums[j] = False
    return [i for i in range(2, n+1) if nums[i] == True]

에라토스테네스의체(2960번)

코드

n, k = map(int, input().split())
count = 0
nums = [True] * (n+1)
for i in range(2, n+1):
    if nums[i] == True:
        for j in range(i, n+1, i):
            if nums[j] == True:
                nums[j] = False
                count += 1
            if count == k:
                print(j)
                break

풀이노트

n번째 수 = list 상에서 n+1번째에 위치하므로 list 수를 (n+1) 개로 정함
m = int(n ** 0.5) 번 돌면 되지만 헷갈려서 n-1회 돌림
nums[j] == True 일 경우는 count 하지 않음
j 가 곧 위치이므로 print(j)를 하면 됨

소수 찾기(1978번)

코드

def eratos(n):
    nums = [True] * (n+1)
    for i in range(2, n+1):
        if nums[i] == True:
            for j in range(i+i, n+1, i):
                nums[j] = False
    return [k for k in range(2, n+1) if nums[k] == True]


answer = 0
n = int(input())
numbers = list(map(int, input().split()))
prime_numbers = eratos(max(numbers))
for n in numbers:
    if n in prime_numbers:
        answer += 1
print(answer)