Python 프라임 검사기 알고리즘
Python을 사용하여 숫자가 소수인지 확인합니다. 효율적인 수학적 반복과 루트 평가를 보려면 대화형 알고리즘을 실행하세요.
개요
소수는 1과 자기 자신 외에 양의 약수가 없는 1보다 큰 양의 정수입니다.
소수를 확인하는 가장 비효율적인 방법은 숫자 자체까지 반복하는 것입니다. 강력한 최적화는 숫자의 제곱근까지만 가분성을 확인하는 것입니다.
코드 및 실행 출력
O(sqrt(n)) 최적화를 보여주는 효율적인 소수 확인 알고리즘.
prime_checker.py
에디터에서 사용해 보세요import math
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
max_divisor = math.isqrt(n)
for i in range(3, max_divisor + 1, 2):
if n % i == 0:
return False
return True
test_numbers = [2, 10, 17, 25, 97]
for num in test_numbers:
status = "Prime" if is_prime(num) else "Not Prime"
print(f"{num:2d} -> {status}")터미널 출력
2 -> Prime
10 -> Not Prime
17 -> Prime
25 -> Not Prime
97 -> Prime단계별 구현
- 암호화 및 해싱 알고리즘
- 교육수학과 체이론
- 보안 키에 대한 백엔드 검증
자주 묻는 질문
왜 제곱근까지만 확인하나요?
$n = a \times b$인 경우 인수($a$ 또는 $b$) 중 적어도 하나는 $n$의 제곱근보다 작거나 같아야 합니다. 따라서 더 높은 값을 확인하는 것은 중복됩니다.