목록에라토스테네스의 체 (1)

말감로그

[백준] 2960번 에라토스테네스의 체 (파이썬)

에라토스테네스의 체 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 동작 과정 1. 2부터 N까지의 모든 자연수를 나열한다. 2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.) 4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다. 에라토스테네스의 체 알고리즘 (파이썬) import math n = 100 #2부터 100까지의 모든 수에 대하여 소수 판별 prime = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화 for i in r..
백준 2024. 4. 8. 15:12
이전 Prev 1 Next 다음