소인수분해 심화응용 - linear sieve와 smallest prime factor 알고리즘 익히기

1. 문제 16563번: 어려운 소인수분해 (acmicpc.net) 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 500만 이내의 값에 대한 100만개의 수가 주어질때 각각을 소인수분해하는 문제 2. smallest prime factor smallest prime factor 알고리즘은 어떤 수의 가장 작은 소인수를 찾아 배열에 저장하는 알고리즘이다. 소인수분해를 수행하는 기본 알고리즘은.. p = 2부터 시작해서 $\sqrt{n}$까지 나눠보면서 소인수를 찾는데 #trivial prime factorizatio..