소수 판별법

• 한 숫자만 검증
  • 기본
    • $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 배열을 사용