Computer Science/알고리즘1 [알고리즘] 소수 판별 : 에라토스테네스의 체 하나의 수가 소수인지 판별할 때는 간단하게 아래와 같이 짤 수 있다. # n : 소수인지 판단할 숫자 is_prime = 1 for i in range(2, n): if n % i == 0: is_prime = 0 소수를 여러번 판별할 경우 에라토스테네스의 체를 사용하는 것이 효율적이다! 10^12 의 큰 수를 소수 판별시 위의 방법 사용 10^6 이하의 모든 소수를 구할때는 에라토스테네스의 체를 활용!! 에라토스테네스의 체 시간 복잡도 O(nloglogn) 어떤 수가 소수가 아닌지를 판정하는 방식으로 동작 2부터 순서대로 그 수가 소수이면 그의 배수들을 모두 소수가 아님! 예시 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 .. 2023. 5. 9. 이전 1 다음