首页 > 代码库 > 素数分组 哥德巴赫猜想
素数分组 哥德巴赫猜想
题目描述
最少把1~n 分成多少组，可以使得每组的数的和为素数
输入
有多组数据
第一行是一个数T，表示数据组数
每组数据共1 行，为正整数n
输出
有T 行，每行为该情况的最少组数，无法分组时，输出-1
样例输入
12
样例输出
1
哥德巴赫猜想裸题
首先如果sum(n)是偶数，即两个素数之和，writeln(2)
如果sum(n)是奇数，那么分类讨论，如果sum(n)是质数，1即可
如果不是素数
check(sum(n)-2),如果是素数，就是3了
关于证明：
我们首先把1~n全部加起来，那么我们相当于把1~n分成了一组
我们知道：任意一个偶数都可以表示为两个质数之和
如果(∑n and 1)=0那么就是2个质数之和了
否则，如果∑n不为偶数，我们还需要分类讨论，
分类为，奇质数和非奇质数，奇质数好说，既然都是质数了，那么直接和就是一组，writeln(1)
否则，我们对于这个非质数，我们拿这个数去减2
2是唯一的偶质数，任意一个大于7的奇数可以表示为三个质数之和
由数学归纳法，若2不在三个质数中，那么往大更不在。
所以若减2之后不是质数writeln(3)即可，否则输出2即可。
判断质数用miller-rabin，大大优化常数
代码如下：
{$inline on}var j,k,l,n,m,s,t:int64; b:boolean; i:longint; a:array[2..6] of integer=(3,5,7,13,19); const count=10; pri:array [0..10] of longint=(2,3,5,7,11,13,17,19,23,29,31); function multi(a,b,m:int64):int64;var ans:int64;begin ans:=0; a:=a mod m; while b<>0 do begin if (b and 1)=1 then begin ans:=(ans+a) mod m; dec(b); end; b:=b>>1; a:=(a+a) mod m; end; exit(ans);end; function gcd(x,y:int64):int64;begin if x mod y=0 then exit(y) else exit(gcd(y,x mod y));end; function quick_mod(a,b,m:int64):int64;var ans:int64;begin ans:=1; a:=a mod m; while b<>0 do begin if (b and 1)=1 then begin ans:=multi(ans,a,m); dec(b); end; b:=b>>1; a:=multi(a,a,m); end; exit(ans);end; function prime(n:int64):boolean;var m,k,a,x,y:int64; i,j:longint;begin if n=2 then exit(true); if (n<2) or ((n and 1)=0) then exit(false); m:=n-1; k:=0; while (m and 1)=0 do begin inc(k); m:=m>>1; end; randomize; for i:=0 to count do begin a:=random(n) mod (n-1)+1; x:=quick_mod(a,m,n); y:=0; for j:=0 to k-1 do begin y:=multi(x,x,n); if (y=1) and (x<>1) and (x<>n-1) then exit(false); x:=y; end; if y<>1 then exit(false); end; exit(true);end; procedure start; inline;var s:int64;begin s:=n*(n+1) shr 1; if n>=7 then if (s and 1)=0 then writeln(‘2‘) else if (prime(s)) then writeln(‘-1‘) else if prime(s-2) then writeln(‘2‘) else writeln(‘3‘); if (n<7) then begin if odd(n) then s:=n*(n shr 1+1) else s:=(n+1)*(n shr 1); m:=s-a[n]; if m=0 then writeln(‘1‘) else writeln(‘2‘); end;end;procedure main; inline;begin read(t); for i:=1 to t do begin read(n); if (n=0)or(n=1) then writeln(‘-1‘) else start; end;end;begin main;end.
素数分组 哥德巴赫猜想
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。