Dev On The Coffee Dev On The Coffee

# 문제 내 풀이 m = int(input()) n = int(input()) # 처음엔 모두가 소수인 것으로 초기화 (0과 1 제외) array = [True for _ in range(n + 1)] array[0], array[1] = False, False # 에라토스테네스의 체 알고리즘 수행 # 2부터 n의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(n ** 0.5) + 1): if array[i]: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j

# 문제 내 풀이 # 2부터 4000000까지의 모든 수에 대하여 소수 판별 (n의 최대 입력) limit_num = 4000000 # 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외) array = [True for _ in range(limit_num + 1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 limit_num의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(limit_num ** 0.5) + 1): if array[i] == True: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j

# 문제 내 풀이 - 시간 초과, 수정 답안 n = 123456 * 2 # 2부터 (2 * 123456)까지의 모든 수에 대하여 소수 판별 # 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외) array = [True for _ in range(2 * n + 1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 2n의 제곱근까지의 모든 수에 대하여 for i in range(2, int((2 * n) ** 0.5) + 1): if array[i] == True: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j 1 and array[i]: cnt += 1 # 개수 출력 print(cnt) 생각해볼 점 에라토스테네스의 체의 시간복잡도가 매우 빠르긴 하지만, 테스트..

# 문제 내 풀이 m, n = map(int, input().split()) # 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외) array = [True for i in range(n + 1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 n의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(n ** 0.5) + 1): if array[i] == True: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j 1 and array[i]: print(i) 생각해볼 점 마지막 출력에서 1을 거르는 조건을 생각하지 못해 오래 걸렸다. 예외 케이스를 항상 염두하자.

# 소수 (Prime Number) 판별 알고리즘 소수란 1보다 큰 자연수 중 1과 자기자신을 제외한 자연수로는 나누어떨어지지 않는 자연수를 말한다. 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제되므로 알고리즘을 기억해두면 좋다. 다음은 기본적인 소수 판별 알고리즘을 파이썬으로 구현한 것이다. # 소수 판별 함수 정의 (2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i in range(2, x): # x가 해당 수로 나누어떨어진다면 if x % i == 0: return False # 소수가 아님 return True # 소수임 print(is_prime_number(4)) print(is..