에라토스

[python] 백준 - 1747. 소수&팰린드롬

🤔문제 해결 G5 | 에라토스테네스의 체, 문자열 소수를 찾고, 그게 소수이면 팰린드롬인지 확인한다. 팰린드롬인지 확인하는 법은 간단하다. 문자를 뒤집어서 같으면 True 브루트포스로 찾아도 문제해결은 가능하지만 에라토스를 쓰는것과 시간이 10배 이상 차이난다. 에라토스테네스의 체를 써서 제한 숫자까지 소수들을 구해놓는다. 그 소수이면서 팰린드롬이면 값을 반환하고 끝 💻소스 코드 def make_eratos(l: int) -> list: eratos = [1] * (l + 1) eratos[0], eratos[1] = 0, 0 for i in range(2, l): if eratos[i]: for j in range(i * 2, l, i): eratos[j] = 0 return eratos def is_..

에라토스테네스의 체(Sieve Of Eratosthenes)

📔 에라토스테네스의 체(Sieve Of Eratosthenes) 란 대표적인 소수 판별 알고리즘 ( 소수: Prime Number ) 한꺼번에 많은 숫자의 소수를 판별할 때 사용 숫자 한개의 소수를 판별하는 기본 소수 판별 알고리즘의 시간복잡도는 O(N) 하지만 수학적으로 접근해서 시간복잡도를 O(N^(1/2)) 까지 줄일 수 있다. 에라토스테네스의 체를 사용하면 시간복잡도는 O(n log log n) 📔 에라토스테네스의 체(Sieve Of Eratosthenes) 구현 자연수 50까지의 숫자 중에서 소수를 구한다고 생각해보자. 기본 알고리즘을 사용할 경우 O(N*N^(1/2)) 의 시간복잡도가 생긴다. 에라토스테네스의 체를 이용하여 구해보자. 먼저 51개의 값이 1(True)인 리스트를 만든다. for..