파이썬에서 소수 세기

제한이 있다고 가정합니다. n. 우리는 2에서 n 사이에 존재하는 소수의 수를 세어야 합니다. 따라서 n =10이면 결과는 4가 됩니다. 10 앞에 4개의 소수가 있으므로 2, 3, 5, 7입니다.

이를 해결하기 위해 우리는 다음과 같은 접근 방식을 따를 것입니다 -

• 카운트 =0
• 크기가 n + 1인 배열 소수 =하나를 가져와 False로 채웁니다.
• i =0에서 n에 대해
  • 프라임[i] =거짓이면
    • 1씩 증가
    • j =2로 설정
    • j * i
    • 소수[i * j] =참
    • j =j + 1

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def countPrimes(self, n):
      """
      :type n: int
      :rtype: int
      """
      count = 0
      primes = [False for i in range(n+1)]
      for i in range(2,n):
         if primes[i] == False:
            count+=1
            j = 2
            while j*i<n:
               primes[j*i] = True
               j+=1
      return count
ob1 = Solution()
print(ob1.countPrimes(50))
print(ob1.countPrimes(10))

입력

n = 50
n = 10

출력

15
4