반응형 파이썬(Python)/알고리즘2 파이썬(Python) - 에라토스테네스의 체 : 범위 내 존재하는 모든 소수 찾기 알고리즘 이전 글에서 소수를 찾는 효율적인 방법을 알아보았다. 파이썬(Python) - 소수 찾기 알고리즘 구현하기(Prime Number) 코딩테스트를 공부하거나 준비하다보면 특정 숫자가 소수(Prime Number)인지 아닌지를 판단해야할 때가 있다. 소수는 1과 자기자신을 제외하면 자연수 중에서 어떤 숫자로도 나누어 떨어지지 않는 coding-of-today.tistory.com 위의 방법을 사용하면 확인하고자 하는 숫자가 소수인지는 파악하는 것은 문제가 없지만, 일정 범위 내에 존재하는 모든 숫자 중에서 소수를 모두 찾으려면 굉장히 오랜시간이 걸리게된다. 모든 숫자를 하나씩 검사해봐야하기 때문이다. 따라서 전혀 다른 방식의 알고리즘을 사용해야하는데 이럴 때 사용할 수 있는 알고리즘이 바로 '에라토스테네스의.. 2021. 11. 30. 파이썬(Python) - 소수 찾기 알고리즘 구현하기(Prime Number) 코딩테스트를 공부하거나 준비하다보면 특정 숫자가 소수(Prime Number)인지 아닌지를 판단해야할 때가 있다. 소수는 1과 자기자신을 제외하면 자연수 중에서 어떤 숫자로도 나누어 떨어지지 않는 숫자를 말한다. 예를들면, 3, 5, 7 같이 말이다. (1은 소수에 포함되지 않는다) 일단 특정 숫자 x가 소수인지 확인하는 가장 간단한 방법은 2에서부터 x-1 까지 모든 숫자를 x에 나눠보고 나눠떨어지는게 있는지 없는지를 확인하는 방법이다. # 특정 숫자 x가 소수인지 판별하는 가장 기본적인 알고리즘 def primenumber(x): for i in range(2, x):# 2부터 x-1까지의 모든 숫자 if x % i == 0:# 나눠떨어지는게 하나라도 있으면 False return False retu.. 2021. 11. 29. 이전 1 다음 반응형