문제
정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.
출력
N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.
예제 입력 1 복사
72
예제 출력 1 복사
2
2
2
3
3
예제 입력 2 복사
3
예제 출력 2 복사
3
예제 입력 3 복사
6
예제 출력 3 복사
2
3
예제 입력 4 복사
2
예제 출력 4 복사
2
예제 입력 5 복사
9991
예제 출력 5 복사
97
103
출처
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | import sys from math import * input = sys.stdin.readline def isPrime(num): if num < 2: return False for i in range(2, int(sqrt(num)) + 1): if num % i == 0: return False return True N = int(input().strip()) num = 2 if N == 1: print('') else : while True: if N == 1: break if isPrime(num) and N % num == 0: N /= num print(num) else: num += 1 |
이거 시간초과 뜨는데 구글링해서 보니까 그냥 소수인지 체크 할 필요 없이 2부터 안나눠질때까지 나눠주고 1씩 더해서 다시 안나눠질때까지 나눠주면 되더라
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | import sys from math import * input = sys.stdin.readline N = int(input().strip()) num = 2 if N == 1 : print('') for i in range(2, N+1): if N % i == 0: while N % i == 0: N /= i print(i) |
이렇게 ;; 생각해보면 이렇게 하면 소수인지 체크 안해도 되는데
이런 발상을 못했음 이거 계속 풀다보면 극복 가능한건가
실버 수학문제들 푸는데 죄다 시간초과떠서 미칠 것 같음 ㅠㅠ
정상인데
내가 처음 보고 작성한 소스는 위에 소스임 ..... 시간초과 떠서 구글링했더니 너무 멍청하게 짯더라고 ..
해당 댓글은 삭제되었습니다.
하 머릿속에 집어 넣었다 .. 사고력 늘려나가야지
소수 찾는법을 잘 생각해보면 이미 거기서부터 나눠대고 있지 ㅇㅇ 한숨 돌리면서 중복을 어떻게 줄일지 계속 생각해보면 쉬워질듯
감사합니다 ㅜ 실버4라 쉬울 줄 알았더니 어렵네요