펭로그

문제링크 : http://codeforces.com/contest/1059 C. Sequence Transformation 각 숫자들을 인수분해 하면 소수들의 곱으로 이루어진다.입력 사이즈가 100만이기 때문에 100만의 제곱근 만큼인 1000까지의 소수를 구하고 그 소수들 중에서 가장 많은 배수들을 가지고 있는 소수를 추려내고 나머지 모든 수를 1로 출력, 그 소수의 제곱수가 아닌 숫자를 그 소수로 출력, 소수의 제곱수를 출력 하는 식으로 문제를 접근했는데.. 답은 맞게 나오겠지만 메모리 공간이 분명 초과되는듯 하다. 기존엔 문제를 이렇게 풀었으나 출력해서 규칙을 보니.. 2의 배수만 신경쓰면 되는 것을 발견했다.3을 제외하고 전부 2로 출력되었으니 말이다.. 12345678910111213141516..