[알고리즘] Count Primes

어느 순간 300명이 제 부족한 글을 읽어주셔서 다시 한번 감사드립니다. 앞으로도 꾸준히 하는 개발자가 되겠습니다. 

강한 놈이 살아남느게 아니라 살아남는 놈이 강한거다.

포인트

1. 이번 문제는 소수 찾기를 하는 문제 입니다. 소수를 찾는 방법은 여러가지가 있으나 제일 유명한 것은 에라토네스 체가 아닐까 싶습니다.. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

class Solution
{
public:
  int countPrimes(int n)
  {
    bool isPrime[5000000];
    for (int i = 2; i < n; i++)
    {
      isPrime[i] = true;
    }
    // Loop's ending condition is i * i < n instead of i < sqrt(n)
    // to avoid repeatedly calling an expensive function sqrt().
    for (int i = 2; i * i < n; i++)
    {
      if (!isPrime[i])
        continue;
      for (int j = i * i; j < n; j += i)
      {
        isPrime[j] = false;
      }
    }
    int count = 0;
    for (int i = 2; i < n; i++)
    {
      if (isPrime[i])
        count++;
    }
    return count;
  }
};

python

class Solution:
    def countPrimes(self, n: int) -> int:

        isPrime = [False,False] + [True] * (n-2)
        i = 2
        while i*i < n :               # Loop's ending condition is i * i < n instead of i < sqrt(n) to avoid repeatedly calling an expensive function sqrt().
            if isPrime[i]:             # if not prime, it is some prime multiple.
                j = i*i                 # ex: we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ...
                while j < n:
                    isPrime[j] = False
                    j += i
            i += 1
        return sum(isPrime)