1 清大100第四题
https://i.imgur.com/E4Vh4wr.jpg
有查过解答知道是用radix sort来做，但尝试跟着写一遍却卡住了，下面是我的过程，最后
的求出来的结果好像怪怪的，想问问我的问题出在哪里
https://i.imgur.com/YVxuczG.jpg
2 清大101第14题
https://i.imgur.com/BoIRNn2.jpg
这题我没查到解答，不太清楚我的想法是不是正确
下面是我尝试解得过程
https://i.imgur.com/rMNUW0d.jpg
我在推n-tuple的解是prime number problem的解时不知道该怎么下手
感谢各位

第14题我的想法是 可以把n-tuple optimization problem修改成decision version 也就是一个数x是否存在n个正整数相乘=x 且这n个数相加小于等于k给定任一个prime number problem 的instance x，可以reduce成n-tuple的instance，也就是是否存在x等于n个正整数相乘，且这n个正整数小于等于K，K取x+n-1上面讲的有点瑕疵抱歉 应该是这样给定一个prime number problem的instance x，reduce成一个decision version的n-tuple optimization problem，也就是是否存在n个正整数相乘等于x，且这n个数相加小于等于K，这边只要n取2 然后取K取x，这样reduce完以后，如果x是prime的话，一定找不到两个数相乘等于x且相加小于等于x，也就是说n-tuple那边会是false；相反的，如果x不是prime，则必定可以找到两个数字相乘等于x且相加小于x，也就是n-tuple那边是true

先感谢N大的回复，想请问最后一句x不是质数的话则必有两数相加小于x且相乘等于x这句该怎么证明呢？

http://i.imgur.com/jWN9JGX.jpg第四题方向大概是这样，有一些细节我没写很详细

感谢b大，我再研究一下

你的问题应该是你取了n进位，你的bucket数应该是n而不是2^(lglgn*lgn), 改掉你就得到O(nlglgn)了

感谢b大 看了你的图我懂了！！

我觉得楼上N大把prime那题弄得有点复杂XD, 令x为我们要test的prime, 设定n = 2, 看他的最小两数和是不是x+1。因为我们一定找得到两个数相乘是x（x和1）,假如最小两数和是x+1，那他就是质数（理由是，譬如说观察12=1*12=2*6=3*4，两数和是不是越来越小，如果是质数那他找到的两数和只能有x+1）相反如果最小总数和小于x+1，那x就不是prime

不是质数的话 只要随便找一个正因子分解x=ab，且a和b都不是1的话，相加起来一定小于x，算是蛮直观的吧，刚刚想了一下要怎么严谨的证明这件事都没有成功QQ

感谢楼上两位大大 我懂了

B大跟我的想法一模一样 感谢补充 我只是想说要写的严谨一点LOL