1929

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