@160149さんから出た問題。

ある整数に掛けて、平方数にする、できるだけ小さなNを求めよ。

bin:sq.exe
i.e.)
sq 3
-> 3
sq 9
-> 1
sq 12
-> 3
sq 20
-> 5

#include 

#include 

#include 

#include 

#include 
typedef std::map Container;
bool is_prime(int n)

{

	using namespace pstade::oven;

	if(n < 2) { return false; }

	if( n % 2 == 0 ) { return n == 2; }

	

	const int sqrt_n = sqrt(n);

	if( sqrt_n <= 2 ) {

		return n == 3 || n == 5 || n == 7;

	}

	

	for(int t = 3; t <= sqrt_n; t +=2 ) {

		if(n % t == 0) { return false; }

	}

	return true;

}
void Analyze(const int n, Container& cont)

{

	using namespace pstade::oven;

	const int sqrt_n = std::max((int)sqrt(n), 2);

	

	if( n < 2 ) { return; }

	

	PSTADE_OVEN_FOREACH(prime, counting(2, sqrt_n+1)) {

		if(is_prime(prime)) {

			if( n % prime == 0 ) {

				cont[prime]++;

				Analyze(n/prime, cont);

				return;

			}

		}

	}

	cont[n]++;

}
int main(int argc, char** argv)

{

	const int n = boost::lexical_cast(argv[1]);

	

	Container cont;

	Analyze(n, cont);
	int cmpl = 1;

	PSTADE_OVEN_FOREACH(c, cont) {

		if(c.second % 2 == 1) { cmpl *= c.first; }

	}

	

	std::cout << cmpl << std::endl;

}

↑gcc4.5.0で確認。pstade::ovenのイテレータアダプタが連結できないので、ちょっと汚いです。
素数判定も別にアルゴリズムを使っているわけではないですしおすし。