전체 글

[Python] 백준(BOJ) 9020번 골드바흐의 추측

9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이..

[알고리즘] 소인수분해

n = int(input()) while n % 2 == 0: # 2로 나누어지면 n에 2를 나누고 2를 출력 n //= 2 print(2) for i in range(3, int(n ** .5) + 1, 2): # 3부터 루트n까지 2씩 증가 while n % i == 0: # i로 나누어지면 n에 i를 나누고 i를 출력 n //= i print(i) if n == 1: break # n == 1 이면 for문 탈출 if n != 1: print(n) # 입력받은 n이 소수이면 아무런 계산도 하지 않고 그대로 나옴 #입력값 72 #출력값 2 2 2 3 3 # 입력값 9991 # 출력값 97 103

[알고리즘] 특정 구간 소수 ( 에라토스테네스의 체 )

m, n = int(input()), int(input()) # 구간을 입력받는다 bool = [False, False] + [True]*(n-1) # 0과 1은 소수가 아니므로 False를 넣어둔다 for i in range(2, int(n**.5)+1): if bool[i]: for index in range(i*2, n+1, i): bool[index] = False # i의 배수에 False를 넣어준다 print([i for i in range(m, n+1) if bool[i]]) # m부터 n까지의 구간에서 bool[i]가 True인 값만 출력 # 입력값 3 20 # 출력값 [3, 5, 7, 11, 13, 17, 19]

[알고리즘] 소수 판정

p = int(input()) # p에 값을 입력받는다 bool = True if p 2 and p % 2 == 0: # p가 2보다 크고 짝수면 소수가 아니다. bool = False else: for i in range(3, int(p ** .5) + 1, 2): # 3부터 p의 제곱근까지 홀수만 나누어 본다 if p % i == 0: bool = False # p가 나누어떨어지면 소수가 아니다 break if bool: print('소수가 맞다') else: print('소수가 아니다') # 입력값 2 # 출력값 소수가 맞다