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

Hoin's security

2.[1주차] baekjoon 1978번 파이썬 문제풀이+에라토스테네스의 체

백준 1978번 문제를 풀어보겠다. 문제는 위와 같다. 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말한다. 이를 판별하는 방법은 입력받은 숫자를 2부터 입력받은 수-1까지 나누어 보았을 때 나누어 떨어지면 소수가 아닌 것으로 찾는 방법과 에라토스테네스의 체 알고리즘을 사용하는 방법이 있다. 전자는 효율이 떨어지기 때문에(속도가 느림.) 후자를 기준으로 살펴본다. 에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이고 N보다 작거나 같은 모든 소수를 찾을 ..
Algorithm/Baekjoon 2023. 9. 18. 14:14
이전 Prev 1 Next 다음