약수와 배수 - 백준 1929

약수와 배수 파트이다.

여기서는 약수와 배수를 빠르게 구하는 방법 그리고 소수를 구하는 일이 주된 문제였다

주로 사용한 알고리즘은 유클리드 호제법이랑 소수를 구하는 알고리즘이였는데

유클리드 호제법은 전에 공부했었기 때문에 재귀함수로 쉽게 풀어냈다.

 

 

 

그리고 소수를 구하는 문제들을 풀다가 에라토스테네스의 채라는 것을 알았다.

일정 범위 내에 있는 소수의 갯수를 빠르게 찾는 방법인데 사용법은 이렇다

num = 100
arr = [False,False] + [True]*(num-1)
for i in range(2,num - 1) :
	if arr[i] :
    	for j in range(2 * i, num, i)
        	arr[j] = False

0부터 100까지의 수를 소수이면 True 아니면 False를 갖는 배열 arr을 만들었다.

원리는 이렇다 소수의 배수들은 전부 소수가 아니므로 False로 바꿔준다.

이렇게하면 arr에는 소수를 판별한 배열이 만들어지고 인덱스를 호출하면 소수인지 아닌지 알 수 있다.

이게 가장 빠른 방법이라고 해서 이를 사용한 풀이도 있지만 나는 소수를 판별하는 함수를 만들어

주어진 범위를 순회하면서 정답을 해결했다.

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

백준 1929번 문제가 에라토스테네스의 채를 사용하면 쉽게 풀 수 있다.

나는 다르게 풀었으니 내가 푼 풀이는 아래 코드를 참고하시길~!~

import math
m,n = map(int,input().split())
def Prime(num) : 
    if num == 1 or num == 1:
        return False
    half = math.sqrt(num)
    isPrime = True
    for i in range(2,int(half) + 1) :
        if num % i == 0 :
            isPrime = False
            break
    if isPrime == True :
        return True
    else :
        return False
result = []
for i in range(m,n+1) :
    isPrime = Prime(i)
    if isPrime == True :
        result.append(i)
print(*result,sep='\n')