백준
[백준 파이썬] 소수 문제 유형 정복하기
파이썬 소수문제 정복하기 한 주간 알고리즘 스터디를 진행하면서 소수 문제를 다루었다. 소수가 사용되는 유형을 정리해두면 도움이 될 것 같아서 정리해보았다. 설명하기 쉬운 코드를 위해 유투브 영상을 일부 참고하였다. 성능 비교를 위해서 time을 측정하였고, input에는 동일하게 5를 넣어 비교해보았다. 소수 여부 판별 # chapter 1 # n이 소수인지 아닌지 판별_약수의 개수를 check 하여 판별 n = int(input()) check = 0 for i in range(1, n+1): # n+1 : n까지 포함하기 위해 ; range 범위의 특성 if n%i == 0: check += 1 if check == 2: print('소수') else: print('소수가 아닌 수') # 5 # 소수..
[백준 파이썬] 에라토스테네스의 체
에라토스테네스의 체 스터디를 통해 이해했던 내용을 바탕으로 정리해보았다. 수학적으로 정확하게 풀어냈다기 보단 스스로 이해한 바를 정리한 것으로 참고만 하길 바란다. 합성수 여부 판단 에라스토테네스의 체를 통해 소수와 합성수 여부를 판단할 수 있다. ※ '소수 2개의 곱를 이용해서 합성수를 만들 수 있다' 는 가정에서 시작한다. N = 6일 때(N>1), 6은 합성수에 해당한다. 합성수는 2개의 숫자 곱으로 표현할 수 있다. 이때 작은 수를 K, 큰 수를 L로 둔다. ex) 6 = 2 * 3 $$ 1