열무의 코딩일기

접근법 소수 시리즈 4탄이다. 어벤저스도 4편이 엔드게임인데 소수도 이제 엔드게임이었으면 좋겠다. 이번 문제도 에라토스테네스의 체를 이용하면 쉽게 풀 수 있다. 에라토스테네스의 체에 대한 자세한 설명은 이전 포스팅에 있으니 참고바란다. (이전 포스팅) 우선 숫자 0이 들어올 때까지 해당 프로그램은 무한루프를 돌아야 한다. 그리고 각 케이스 별로 입력값이 주어지면 입력값의 두배에 해당하는 범위까지의 소수의 개수를 찾아야한다. 따라서, 이전에 만들어 두었던 프로그램을 활용하면 손쉽게 문제를 풀 수 있다. 풀이 while True: n = int(input()) N = 2 * n if n == 0 : break else : arr = [i for i in range(N+1)] arr[1] = 0 for i i..

접근법 소수 시리즈의 3탄이다. 소수가 싫어진다 소수 2탄과 유사한 문제의 형태이다. 범위가 주어지고, 해당 범위 안에서 소수를 찾는 문제다. 이번에는 전에 사용했던 함수들의 문제점을 조금 해결해보았다. 우선, for문의 반복 범위를 제곱근까지만 돌 수 있도록 변경했다. 반복의 횟수를 줄이는 것만으로 해도 충분히 시간을 줄일 수 있었고, 추가적으로 중간에 나누어 떨어지는 수가 있는 경우에는 즉시 False를 return하도록 했다. 그 코드는 바로 다음과 같다. import math def Prime(num): if num==1: return False n=int(math.sqrt(num)) for i in range(2,n+1): if num%i==0: return False return True M,..

접근법 어찌 되었던 소수를 찾아서 리스트에 담던, 누적합을 시켜주어야 한다. 따라서 전에 생성해두었던 함수를 재활용해 보았다. 함수는 다음과 같다. (이전 포스팅 참고) def Prime(n): if n

접근법 우선 소수의 정의를 확실하게 이해할 필요가 있다! 위처럼 약수가 단 두 개, 자기 자신과 1을 가지는 수를 소수라고 한다. 문제는 주어진 입력 값들 중에서 소수가 몇 개인지 Counting 하는 것이므로 , 필자는 주어진 입력 값까지 차례로 나누어 떨어지는 수가 있는지 판별하여 소수일 경우에는 1을 return하고 그렇지 않을 경우에는 0을 리턴하도록 함수를 생성해 보았다. 풀이 def Prime(n): if n