解説

この問題は、`57`を素数は素数であるという主張のもと、はじめに`57`で割り切ったのち、試し割法などの通常の素因数分解をすることによって解くことができます。
計算量は`O(\sqrt{N})`であり。十分高速です。

---

解答例(C++)

#include<bits/stdc++.h>
using namespace std;

int main() {
	long long N;
	cin >> N;
	vector<long long> answer;

	// 57で割り切る
	while (N % 57 == 0) {
		answer.push_back(57);
		N /= 57;
	}

	// 通常の素因数分解(試し割法)
	while (N % 2 == 0) {
		answer.push_back(2);
		N /= 2;
	}
	long long p = 3;
	while (p * p <= N) {
		if (N % p == 0) {
			answer.push_back(p);
			N /= p;
		}
		else p+=2;
	}
	if (N != 1) answer.push_back(N);

	sort(answer.begin(),answer.end());
	int siz = (int)answer.size();
	for (int i = 0; i < siz; ++i) {
		cout << answer[i] << " \n"[i == siz -1];
	}
}

---

解答例(Python)

def prime(n):
    a = []
    while(n%57==0):
        a.append(57)
        n//=57
    while(n%2==0):
        a.append(2)
        n//=2
    p=3
    while p*p<=n:
        if(n%p==0):
            a.append(p)
            n//=p
        else:
            p+=2
    if n != 1:
        a.append(n)
    return sorted(a)
print(*prime(int(input())))

---

コメント

解説を「57は素数ではありません」から始めようか迷いました。