STEP 9. 약수, 배수와 소수

[letsjo]

단계 설명

약수와 배수는 정수론의 시작점이라고 할 수 있습니다.

문제 / 코드보기

• 배수와 약수 / 코드보기
• 약수 구하기 / 코드보기
• 약수들의 합 / 코드보기
• 소수 찾기 / 코드보기
• 소수 / 코드보기
• 소인수분해 / 코드보기

새로 알게된 점

• 소수 판별 방법1: 시간복잡도 O(N) 절반으로 줄이기

   def isPrime(number):
       if (number < 2):
           return False
       for i in range(2, math.ceil(number/2)+1):
           if (number % i == 0):
               return False
       return True

• 소수 판별 방법2: 시간복잡도 O(log N)

   def isPrime(number):
       if (number < 2):
           return False
       i = 2
       while (i*i <= number):
           if (number % i == 0):
               return False
           i += 1
       return True

• 에라토스테네스의 체: 소수 그룹 찾기

   def solution(number):
       # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제와)
       array = [True for i in range(number + 1)]
   
       # 에라토스테네스의 체 알고리즘
       for i in range(2, int(math.sqrt(number)) + 1):  # 2부터 n의 제곱근까지의 모든 수를 확인하며
           if array[i] == True:  # i가 소수인 경우(남은 수인 경우)
               # i를 제외한 i의 모든 배수를 지우기
               j = 2
               while i * j <= number:
                   array[i * j] = False
                   j += 1
   
       return array
  
   array = solution(100)
  
   # 필요한 소수 범위 출력하기
   for i in range(60, 101):
       if array[i]:
           print(i, end=" ")