[2학기 7주차] 다음 소수, 수열

문제

정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

---

import math
import sys

input = sys.stdin.readline 

T = int(input())
for _ in range(T):
    n = int(input())
    
    p = max(2, n)
    
    while True:
        is_p = True
        
        if p % 2 == 0 and p > 2:
            is_p = False
        else:
            limit = int(math.sqrt(p))
            for i in range(3, limit + 1, 2):
                if p % i == 0:
                    is_p = False
                    break
        
        if is_p:
            sys.stdout.write(str(p) + '\n')
            break
        
        p += 1

 

1. 제곱근 계산을 위한 math 모듈과 빠른 입출력을 위한 sys 모듈 불러오기

2. 표준 입력함수를 더 빠른 sys.stdin.readline으로 대체

3. 테스트 케이스의 개수 T를 입력받음

4. 다음을 T번 반복

5. n을 입력 받음

6. 2와 n중 더 큰 값을 선택해 p라 함

7. 숫자 p가 소수라고 가정하고 판별 시작

8. 만일 p가 2의 배수이고 2보다 크면 p는 소수가 아님

9. 그렇지 않을 경우 limit을 p의 제곱근이라고 설정하고 3부터 limit까지 i가 홀수일때만 다음을 시행

10. 만일 p가 i로 나누어 떨어지면 p는 소수가 아니고, 반복을 종료

11. 만일 p가 소수이면 소수p를 공백과 함께 출력하고 반복 종료

12. 소수를 찾지 못했다면 p를 1 증가시켜 검사 

 

---

 

 

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

---

import sys

N, K = map(int, sys.stdin.readline().split())
temperatures = list(map(int, sys.stdin.readline().split()))

current_sum = sum(temperatures[:K])
max_sum = current_sum

for i in range(K, N):
    current_sum = current_sum - temperatures[i - K] + temperatures[i]
    if current_sum > max_sum:
        max_sum = current_sum

print(max_sum)

 

1. 입력받은 수를 정수로 변환해 N, K에 저장

2. 입력받은 것을 각각 정수로 변환해 리스트에 저장

3. current_sum은 temperatures의 0번째부터 k-1번째 인덱스까지 더한 값

4. current_sum을 max_sum에 저장

5. current_sum은 이전 current_sum에서  i-k번째 온도(가장 이전온도)를 빼고  i번째 온도(가장 최근 온도)를 더한 값

6. 만약 current_sum이 max_sum보다 크면 current_sum을 max_sum이라 지정

7. 최종값 max_sum 출력