BOJ 2312 수 복원하기
4946 단어 2021.02.052021.02.05
https://www.acmicpc.net/problem/2312
시간 2초, 메모리 128MB
input :
- 테스트 케이스의 수
- N (2 ≤ N ≤ 100,000)
output :
- 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력
- 인수가 증가하는 순
각 소인수들을 배열에 넣어넣고 나올때 마다 체크를 해서 할 까 했는데.
좋은 카운터를 이용하기로 했다.,
근데 most_common 메소드를 쓰면 가장 많이 나온 인수 순서대로 나오니까.
인수가 증가하는 순서로 나오게 하기 위해 정렬을 해주자.
import sys
from math import sqrt
from collections import Counter
minFactor = [i for i in range(100001)]
for i in range(2, int(sqrt(100001))):
for j in range(i * i, 100001, i):
if minFactor[j] == j:
minFactor[j] = i
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
ret = []
while n > 1:
ret.append(minFactor[n])
n //= minFactor[n]
prime_numbers = Counter(ret)
temp = prime_numbers.most_common()
temp.sort()
for key, value in temp:
print(key, value)
Author And Source
이 문제에 관하여(BOJ 2312 수 복원하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-2312-수-복원하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)