狐狸太郎和次郎正在玩一款名为 Prime Hazard 的电脑游戏。
Prime Hazard中出现的角色上写有大于2的整数,写有素数的角色是玩家的同伴,写有合数的角色是玩家的敌人。
玩家必须看着角色上写的数字,立即判断自己是敌人还是盟友,并只攻击敌人。输入写在敌人身上的数字的最小质因数即可击败敌人。
太郎和二郎在玩这个游戏时决定角色划分如下。
- 太郎读取敌人的数量并将该信息转发给二郎。
- 根据太郎提供的信息,二郎判断该角色是否是敌人,如果是,则最小质因数是多少。
由于我们必须一次处理大量字符,因此我们希望使信息通信尽可能简单。太郎决定告诉二郎一些数字,0或1。
課題
大于或等于 2 的正整数 判断N被给予。N是否是素数。对于合数,找到最小的质因数。
执行以下程序:
- 具有以下参数的过程 芋头(N):
- N -- 给定的正整数。
- 具有以下参数的过程 二郎(S, X)
在:
- S -- 从 Taro 发送的数据的长度(位数)。
- X -- S 整数的一维数组。0 ≤ i < S 对于 反对 X[i] 是 它仅由 芋头(N) 里面 发送(b) 通过重复调用 是 在 i+1 被呼叫时 等于 b 的值。
例
例1
N = 7 考虑
的情况。
芋头 里面 发送 假设 被这样调用:
| 发送(1) |
| 发送(1) |
| 发送(0) |
| 发送(1) |
此时 二郎 通话中 S = 4 和
| X = | 1 |
| 1 | |
| 0 | |
| 1 |
变为。
在这种情况下,7 是质数,所以 必须返回二郎 是 它仅由 -1 。
例2
N = 6
的情况。
在这种情况下,6 是一个合数,最小的质因数是 2,所以 二郎 是 它仅由 2 。
小課題
小課題 1 (50 点)
- 2 ≤ N ≤ 1 000
- Taro 发送给 Jiro 的数据大小(S) 是 必须小于或等于 12 。
小課題 2 (50 点)
- 2 ≤ N ≤ 1 000 000 000
- Taro 发送给 Jiro 的数据大小(S) 是 必须小于或等于 12 。
实施细节
制限
- CPU时间限制:1秒
- 内存限制:64 MB
注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。
接口 (API)
- 实现文件夹:primehazard/(原型: primehazard.zip)
- 参赛者实现的文件:primehazard.cpp
注意: 请注意,虽然从提交的文件生成了一个可执行文件,但在判断服务器上启动了两个执行实例。特别是在使用全局或静态变量时。 请注意,您不能与芋头和二郎共享这些变量。 - 提交文件接口:primehazard.h
- 评分程序接口:grader.h
- 评分程序示例:grader.cpp
- 评分程序的示例输入:grader.in.1、grader.in.2、...
注意:示例评分程序按以下格式读取输入。 写入- 1 行目: 整数 N 。N 表示给定的正整数。
- 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
注意:示例评分程序按以下格式写入输出。- 第 1 行:过程 写入 二郎 应返回的值。
- 问题建议:qnighy
- 问题陈述:utatakiyoshi