Seongkyun Han's blog

190211 백준 알고리즘 문제풀기

11 Feb 2019 | baekjoon

[4948] 베르트랑 공준

문제

  • 입력되는 수 n에 대해 n보다 크고 2n보다 작거나 같은 소수의 갯수를 출력

정답

import sys
import math

def isprimenum(num):
    if num <= 1:
        return 0
    for j in range(2, int(math.sqrt(num))+1):
        if num/j == 1:
            break
        if num%j == 0:
            return 0
    return 1

result = 0
while(1):
    num = int(sys.stdin.readline())
    if num == 0:
        break
    else:
        result = 0
        for j in range(num+1, 2*num+1):
            result += isprimenum(j)
        print(result)

[9020] 골드바흐의 추측

문제

  • 골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것
    • 즉, 4=2+2, 14=7+7로 모든 짝수는 두 소수의 합으로 출력 가능하다는것을 의미
  • 첫째 줄에 테스트 케이스, 주어지는 수는 짝수로 주어짐
  • 경우의 수가 많은 경우, 두 소수의 차가 적은 수를 출력해야 함
    • 이를 이용해, for loop를 돌때는 끝 수(주어지는 )의 절반부터 마지막까지 돌면 속도가 빠르게 문제도 해결 가능

정답

import sys
import math

def isprimenum(num):
    if num <= 1:
        return 0
    for j in range(2, int(math.sqrt(num))+1):
        if num/j == 1:
            break
        if num%j == 0:
            return 0
    return 1

for _ in range(int(sys.stdin.readline())):
    num = int(sys.stdin.readline())
    fnum = 0
    lnum = 0
    for j in range(int(num/2), num+1):
        if isprimenum(j) == 1:
            fnum = j
            lnum = num - fnum
        if isprimenum(lnum) == 1:
            print(lnum, fnum)
            break

Related Posts