글 읽기 - 9020 + 에라토스테네스의 체에 관한 질문.

sween9812 1년 전 0

안녕하세요.

1. 아래 코드의 6행에서 range의 범위 중 int(math.sqrt(n)+1) 가 이해 가지 않습니다.

n 의 최대 약수가 sqrt(n) 이하이기 때문이라고 하는데(https://ko.wikipedia.org/wiki/...)

n 의 최대 약수가 왜 sqrt(n)이하인지 모르겠고, 범위로 설정해준 이유인지 모르겠습니다.

2. 아래 코드를 실행하면 결과로 (3, 5) 처럼 '()' 표시가 같이 나오는데 이 괄효 표시를 없애줄 수 있는 방법이 있을까요?

좋은 하루 되세요. 감사합니다.

import math

def prime_list(n):
    array = [True for x in range(n+1)]  # index 0 ~ n 까지 

    for i in range(2, int(math.sqrt(n)+1)): 
        if array[i] == True:
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1
    
    prime_array = [i for i in range(2, n) if array[i] == True]
    
    a = n // 2
    b = n - a

    while a and b not in  prime_array:
        a -= 1
        b += 1 
    return a, b

t = int(input())

for i in range(t):
    n = int(input())
    print(prime_list(n)) 

djm03178 1년 전 1

최대 약수가 sqrt(n)인 것이 아니라, sqrt(n)까지를 모두 나누어보면 모든 약수를 구할 수 있다는 뜻입니다.

만일 어떤 x가 n의 약수라면 n / x 역시 n의 약수인데, sqrt(n)보다 x가 크다면 n / x는 sqrt(n)보다 작아야 하기 때문입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

9020 + 에라토스테네스의 체에 관한 질문.

sween9812 1년 전 0

djm03178 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말