소수 판별 알고리즘

#2022. 9. 7. 알고리즘 수업

소수 판별 알고리즘의 복잡도 줄이기

1. 복잡도 O(n)

n = int(input())

is_prime = True

for i in range(2, n):
    
    if n % i == 0:
        is_prime = False
        break
 
if is_prime:
    print(f"{n} is a PRIME NUMBER.")
else:
    print(f"{n} is NOT a prime number.")
    

2. 복잡도 O(√n)

n = int(input())

is_prime = True

for i in range(2, math.sqrt(n)+1):
    
    if n % i == 0:
        is_prime = False
        break
 
if is_prime:
    print(f"{n} is a PRIME NUMBER.")
else:
    print(f"{n} is NOT a prime number.")
    

합성수 (Composition number)는 두 수의 곱으로 표현된다.