소수 판별법

• 한 숫자만 검증
  • 기본
    • $1\sim \sqrt{n}$까지 곱셉 비교 i * i <= n

    •   bool is_prime(int n) {
            if (n <= 1) return false;
            if (n == 2) return true;
            if (n % 2 == 0) return false;
        
            for (int i = 3; i * i <= n; i += 2) {
                if (n % i == 0) return false;
            }
            
            return true;
        }

  • 밀러-라빈 방법
    • 페르마의 소정리 기반
    • 밀러-라빈 테스트
• 여러 숫자 검증
  • 에라토스테네스의 체
    • 특정 범위까지 2의 배수... n의 배수 false 판별한 brutal force 배열을 사용

    •   vector<bool> t(b + 1, true);
        t[1] = false;
        
        for (int i = 2; i <= sqrt(b); ++i) {
        	if (!t[i]) {
        		continue;
        	}
        	for (int j = i * i; j <= b; j += i) {
        		t[j] = false;
        	}
        }

    • sqrt(n) 까지만 비교하는 이유
      • 합성수 라면 $a\ast a<a\ast b=n;a<=\sqrt{n}$
      • 작은 값으로 나눠지는 경우를 확인
        • a 작은 값, b 큰 값
    • j = i * i로 시작하는 이유
      • 이전 i의 가능값 (2, 3, 4, ... i)에서 배수로 이미 걸러졌기 때문
        • i = 5 인경우
          • i * 1, i * 2, i * 3, i * 4가 이미 이전에 판단완료