[v.기본 수학 2-소인수분해.11653]BAEKJOON_Python

220111 작성

<본 블로그는 BAEKJOON 을 참고해서 저만의 풀이를 작성하였습니다>

 

 

 

11653

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력
N이 1인 경우 아무것도 출력하지 않는다

 

내 풀이

a, b = map(int, input().split())
for i in range(a, b+1):
    count = 0
    if i == 1 :
        continue
    for j in range(2, i+1) :
        if i % j == 0 :
            count += 1
    if count == 1:
        print(j)

얘로도 소수가 나오는데 시간초과!!!

 

에라토스테네스의 체를 사용하라고 한다..

그게 무엇이냐!

특정한 숫자의 제곱근까지만 약수의 여부를 검증하는 방식이당

대량의 소수 한꺼번에 판별 가능!

def isPrime(n) :
    if n == 1:
        return False 
    else :
        for i in range(2, int(n**0.5) + 1) :
            if n % i == 0 :
                return False
        return True

a, b = map(int, input().split())
for i in range(a, b+1):
    if isPrime(i) :
        print(i)

전꺼랑 비슷하지만!

에라토스테네스의 체

이런식으로 1을 제거, 2 소수 제거 + 배수, 3의 소수 제거 + 배수 등등.. 이케 걸러진다

 

 

 

 

내 출력

20
2
2
5

 

 

 

 

 

힝... 

아래거 참고해써여!!!!!!!!!

https://kbwplace.tistory.com/76

[Python/파이썬] 백준 알고리즘 1929번 - 소수 구하기