Noi模拟 质数 哥巴赫猜想

质数(prime)

【题目描述】

将1~n分成尽可能少的集合,使得每个集合的元素和均为质数。

【输入数据】

一行一个正整数n。

【输出数据】

第一行一个正整数m表示最少集合数,第二行n个[1,m]中的整数,第i个整数表示i在第几个集合中。若有多种方案输出任意一种即可。若无解输出-1。

【样例输入】

8

【样例输出】

2

1 2 2 1 1 1 1 2

【数据范围】

对于30%的数据,n<=20。

对于100%的数据,n<=6000。

/////////////////////////////////////////////////////////////////////

哥巴赫猜想:任一大于2的偶数都可写成两个质数之和。

考场上的时候我自己想到了一个猜想,任意一个合数都可以写成两个素数和的形式.,后来发现非常的错误……100以内错误就一大片,后来自己YY了一些结论,然后只有50分。。。。惨

旁边的大佬们分分都想到了哥巴赫猜想。忽然想起UOJ群里有一张图,”他证明了哥巴赫猜想,怕引起轰动,所以撤回了“。

不扯了,讲正解。

先判断和是不是素数。如果是素数,则是1。

如果和是偶数,则是2。我们可以枚举一下由哪两个素数组成就好了。然后我们从大到小,一次尝试填充其中一个数,剩余的就是另外一个集合了。

如果是奇数,我们考虑奇数只能拆成一奇,一偶,而偶数的素数只有2,我们先看看是不是2和一个素数的和。如果能就同上处理即可。如果不行,集合数会继续增加,不如使用下面的方法,稳定3次解决。

如果上面的方法不行,我们选出一个3,然后剩下一个偶数,同偶数情况处理就好了,是3个集合。

发表评论