题解 AT50 【合成数を倒せ (Prime Hazard)】

· · 题解

打倒合成数(prime hazard) 时间限制: 1sec / 内存限制: 64 mb 太郎和次郎都在玩“打倒合成树”的游戏

背景 prime hazard里登场的角色都写着2以上的整数，写有素数的角色是玩家的伙伴，而写合数的角色是玩家的敌人。

玩家们看到的是角色所写的数字，必须瞬间判断敌人或同伴，攻击敌人。敌人可以通过输入所写的数字的最小的因数而被推翻。

太郎和次郎在玩儿这个游戏的时候决定如下分工合作。

太郎读了敌人的数字后，将那个信息传达给次郎。

次郎根据太郎的信息，判断角色是否是敌人，如果是敌人，那么最小的因数

因为必须一次处理大量的角色，所以想尽可能简单地传达信息。太郎决定向次郎发送一个0或1个数字。

题目描述 给出2个以上的正整数n。确定n是质数。如果n是一个合数，求出最小的因数

实现下一个过程:

具有下列参数的过程中(n):

被给予的正整数。

通过在该程序中反复地调用send(b)，能够向次郎发送数据。然而，b必须是0或1。这个过程比jiro(s、x)先被调出1度，没有返回值。

有次参数的过程jiro(s, x):

s --太郎送来的数据的长度(比特数)。

x——1维排列。对0≤i < s [i]等于在taro(n)中send(b)在i+1次被调用时的b的值。

在taro(n)被传唤之后，这个过程只会被传唤。该过程中，如果n为素数，则需要将最小的因数作为返回值。

样例数据 输入#1 n=7

输出#1 1

说明#1 考虑情况。

太郎会这样传送信息

send(1)

send(1)

send()

send(1)

此时，太郎信息传送s = 4

x = 1

1

0

1

在这种情况下，7是质数，因此次郎必须返回到1。

输入#2 n=6

输出#2 2

说明#2 考虑情况。

在这种情况下，六是合成数目，最小的原因是2，因此次郎必须返回2。

简单的数据(50分)

保证2≤n≤1万

太郎送给次郎的数据的大小(s)必须在12以下。

另外的数据(50分)

保证2 ≦ N ≦ 1 000 000 000

太郎送给次郎的数据的大小(s)必须在12以下。

注意 堆栈的大小没有规定的限制。作为堆栈使用的存储器包含在存储器总使用量中 这个是讨论上某个大佬翻译的，萌新摘过来，不算抄袭吧。。。反正宝宝也不会。。。