소수

[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..

[python] 백준 - 4948. 베르트랑 공준

🤔문제 해결 S2 | 에라토스테네스의 체 에라토스테네스의 체를 사용하여 소수를 구하고 시작. 주어진 구간에 맞게 소수의 개수를 꺼냄 💻소스 코드 import sys def eratos(n): for j in range(n * 2, 123456 * 2 + 1, n): dp[j] = 0 dp = [1] * (123456 * 2 + 1) dp[0], dp[1] = 0, 0 for i in range(2, 123456 * 2 + 1): if dp[i] == 1: eratos(i) input = sys.stdin.readline while True: N = int(input()) if N == 0: # 입력 마지막 break print(sum((dp[N + 1:N * 2 + 1]))) 📕문제 확인 출처: BACK..

[python] 백준 - 1929. 소수 구하기

🤔문제 해결 S2 | 에라토스테네스의 체 소수: 1과 자기 자신 이외의 약수를 가지지 않는 1보다 큰 자연수 숫자 하나하나를 모두 for문을 돌려서 구할 수 있지만 비효율적임. 에라토스테네스의 체를 이용한다. 0부터 구하고자하는 값의 길이 만큼 0의 값을 가진 배열을 만든다. ex) dp = [0, 0, 0, 0, ..., 0] for문으로 2부터 배열의 끝까지 돌면서 자기 자신을 제외한 배수는 전부 1로 바꿔준다. 맨 위의 그림을 보면 이해하기 쉬움 배열에서 0인 녀석들을 print해준다. 💻소스 코드 def eratos(n): for j in range(n * 2, E + 1, n): dp[j] = 1 return S, E = map(int, input().split()) dp = [0] * (E +..