소수 찾기 & 숫자 뒤집기

어떤 숫자 n의 약수는 자기 자신의 절반 이하까지만 존재한다는 점을 기억하자. 즉 자기 자신을 제외한 약수는 항상 n/2 이하라는 의미이다. 예를 들어 숫자 16이 주어질 때

1 x 16

2 x 8 을 보면 1과 자기 자신을 제외하면 16의 약수는 2 x (16의 절반)이기 때문에

절반 이하까지만 존재한다.

다시 말해 어떤 수 n의 약수는 자기 자신을 제외하면 항상 n/2 이하이다.

def isPrime(x):
    if x==1:	# 1은 소수 아님
        return False
    for i in range(2, x//2+1):	# x//2+1로 설정해야 x의 절반인 x/2이하까지 탐색
        if x%i==0:
            return False
    else:
       return True

 

 

x//2이 아닌 √x까지 검사하면 보다 빠르게 소수를 판별할 수 있다.

 

어떤 수 n이 소수가 아닌 합성수라면

n는 두 개의 자연수 a, b의 곱으로 표현할 수 있다.

여기서 만약 a, b 모두 √n보다 크다면, a, b의 곱은 n를 초과하게 된다.

즉 a x b = n를 만족하는 약수 쌍 중에서 적어도 하나는 반드시 √n이하이다. 예를 들어 36의 약수 쌍은

(1, 36) (2, 18) (3, 12) (4, 9) (6, 6) 으로 약수 쌍 중에서 하나는 반드시 √36=6이하이다. 따라서 6까지만 검사하면 36이 소수가 아님을 알 수 있다.

37을 예로 들면 √37=6.xxx로 2, 3, 4, 5, 6으로 나눠봐도 나누어떨어지지 않으므로 소수이다.

 

2부터 n//2까지 검사하면 시간 복잡도는 O(x)이고

2부터 √n까지 검사하면 시간 복잡도는 O(√x)로 줄어든다.

 

 

숫자 뒤집기

def reverse(x):
    res=0
    while(x>0):
        t=x%10
        res=res*10+t
        x=x//10
    return res