LeetCode Day 26 - 계수 질 수

2275 단어
204. 계수 질 수
묘사 하 다.
  • 비 음수 정수 n 보다 작은 모든 질량 수의 수량 을 통계 한다.

  • 예시
        : 10
        : 4
        :    10        4  ,     2, 3, 5, 7 。
    

    사고의 방향
  • 한 번 에 2 ~ n 질 수의 수량 에서 돌아 오고 핵심 알고리즘 은 한 수의 질 수 를 판단 하 는 것 으로 전환 된다.
  • 질 수의 글자 에 따라 한 수 는 1 과 자신 에 의 해 정 제 될 수 있 는 것 이 바로 질 수 이 고 2 ~ m - 1 로 차례대로 여 가 를 구 할 수 있 으 며 0 이면 질 수 가 아니다.
  • 최적화 점: 2 ~ m - 1 이 아니 라 2 ~ √ m 만 옮 겨 다 닐 수 있 습 니 다. 만약 에 m 가 2 ~ m - 1 사이 의 모든 정수 에 의 해 정 리 될 수 있다 면 그 두 가지 요 소 는 반드시 1 개 는 √ m 보다 작 거나 같 고 다른 하 나 는 √ m 보다 크 거나 같 기 때 문 입 니 다.예 를 들 어 16 은 2, 4, 8 로 나 눌 수 있 고 16 = 28, 2 는 4 보다 작 으 며 8 은 4 보다 크 고 16 = 44, 4 = √ 16 이기 때문에 2 ~ 4 사이 에 인자 가 있 는 지 없 는 지 판정 하면 된다.
  • 상기 방안 은 정확 하지만 예상 시간 을 초과 했다.간단하게 추산 해 보면 대략 O (n * n) 등급 의 복잡 도 이다.최적화 방향 은 공간 을 이용 하여 시간 을 바 꾸 고 크기 가 n 인 bool 형 배열 을 유지 하 는 것 이다. x 판단 이 끝 난 후에 배열 안의 모든 x 의 배 수 를 false 로 설정 하고 한 수의 질 수 를 판단 할 때마다 먼저 표를 검사 하고 표 안에 있 는 사람 이 있다.
  • 최 적 화 된 해석: 에 라 토스 테 니 체 법 (참고)
  • -                    ,    1~m-1             ,            
    -     1~√n,  √n              ,             ,  √n*√n >= n
    
    class Solution_204_01 {
     public:
      int countPrimes(int n) {
        int cnt = 0;
        for (int i = 2; i < n; ++i) {
          if (isPrime(i)) ++cnt;
        }
        return cnt;
      }
      bool isPrime(int m) {
        for (int i = 2; i <= sqrt(m); ++i) {
          if (m % i == 0) return false;
        } 
        return true;
      }
    };
    
    class Solution_204_02 {
     public:
      int countPrimes(int n) {
        bool pArray[n + 1] = {0};
        int cnt = 0;
        for (int i = 2; i < n; ++i) {
          if (!pArray[i] && isPrime(i)) {
            ++cnt;
            for (int j = i; j < n; j += i) pArray[j] = true;
          }
        }
        return cnt;
      }
      bool isPrime(int m) {
        for (int i = 2; i <= sqrt(m); ++i) {
          if (m % i == 0) return false;
        }
        return true;
      }
    };
    
    class Solution_204_03 {
     public:
      int countPrimes(int n) {
        bool notPrime[n+1] = {0};
        int cnt = 0, limit = sqrt(n);
        for (int i = 2; i <= limit; ++i) {
          if (!notPrime[i]) {
            for (int j = i * i; j < n; j += i) {
              notPrime[j] = true;
            }
          }
        }
        for (int i = 2; i < n; ++i) {
          if (!notPrime[i]) ++cnt;
        }
        return cnt;
      }
    };
    

    좋은 웹페이지 즐겨찾기