TIL 코딩공장

20240421 백준 파이썬 공부
4134번 다음 소수

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

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

3. 출력
각각의 테스트 케이스에 대해서 
n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

>>>코드

import sys
import math
# 소수 검사 함수
def primenum(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n%i == 0:
            return False
    return True
# 테스트케이스와 n 입력받기
for _ in range(int(input())):
    n = int(sys.stdin.readline().strip())
    # n이 2보다 작거나 같은경우
    if n <= 2:
        print(2)
    # 이외의 경우
    else:
        while True:
            if primenum(n):
                print(n)
                break
            n += 1

>>>문제링크
https://www.acmicpc.net/problem/4134

20240313 백준 파이썬 공부
1929번 소수 구하기

1. 문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) 
M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

3. 출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

>>>코드1. 실패 >> 방식은 맞으나 시간초과

m, n = map(int, input().split())
for i in range(m, n+1):
    t = True
    if i != 1:
        for j in range(2, i):
            if i%j == 0:
                t = False
                break
        if t == True:
            print(i)

해당 숫자까지 검사를 하면 시간 복잡도가 높아져서 시간초과가 나온다.
해결 방법은 다음과 같다. 
모든 약수는 제곱근을 기준으로 쌍을 이루므로 제곱근까지만 약수 검사를 진행하면 된다


>>>코드2. 성공 >> 원래 코드 고치기

import math

m, n = map(int, input().split()) # 두 수 입력받기
for i in range(m, n+1): # m 부터 n까지 수 검사하기
    t = True
    if i != 1: # 1이 아닌 경우(1은 소수가 아님)
        for j in range(2, int(math.sqrt(i))+1):
            if i%j == 0:
                t = False
                break
        if t == True:
            print(i)

>>>코드3. 성공 >> 함수 따로 만들기

import math
# 소수 검사함수
def primenumber(n):
    if n == 1: # 1인 경우 소수 아님
        return False
    else: # 1이 아닌경우
        for i in range(2, int(math.sqrt(n))+1): # 2부터 해당 숫자의 제곱근+1까지 검사
            if n % i == 0: # 나누어 떨어지면 소수 아님
                return False
        return True # 결국 나누어 떨어지지 않으면 소수
        
m, n = map(int, input().split()) # 두 수 입력받기
for i in range(m, n+1): # m 부터 n까지 수 검사하기
    if primenumber(i) == True: # 검사 결과가 True일 경우 출력
        print(i)

    
    >>> 문제 링크

https://www.acmicpc.net/problem/18111