Python에서 n보다 작은 소수 목록 생성

숫자 n이 있다고 가정하고 n보다 작은 모든 소수의 목록을 오름차순으로 생성해야 합니다. 1은 소수가 아님을 명심해야 합니다.

따라서 입력이 12와 같으면 출력은 [2, 3, 5, 7, 11]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• sieve :=크기가 n+1인 목록 및 True로 채우기
• primes :=새 목록, 처음에는 비어 있음
• 2~n 범위의 i에 대해 다음을 수행합니다.
  • sieve[i]가 True이면
    • 소수 끝에 i 삽입
    • i에서 n 사이의 j에 대해 i만큼 각 단계에서 업데이트합니다. do
      • 체[j] :=거짓
• 소수 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, n):
      sieve = [True] * (n + 1)
      primes = []
      for i in range(2, n + 1):
         if sieve[i]:
            primes.append(i)
            for j in range(i, n + 1, i):
               sieve[j] = False
      return primes
ob = Solution()
print(ob.solve(12))

입력

12

출력

[2, 3, 5, 7, 11]