枚举原理:对偶质数原理。
歌德巴赫猜想是要证明:大于4的偶数可以写成两个质数的和。
可转化为:对任意一个整数存在一对与该整数前后距离相等的两个质数。
即:对于任意n,存在d,使得 n + d ,n - d 为质数。其中:d < n
程序使用多线程编写。
程序不出错自动停机则表示:歌德巴赫猜想不成立——我们要有耐心等程序运行
程序不停机:歌德巴赫猜想成立——可能等来的是溢出错误;
意义:
科学计算问题面向对象程序设计示范;
运行界面如下:
节选源码:
//1> 1,2是质数,记入已有质数表,2记入未检验对偶数列表
//2> 取下一个数(第1次为3)
//3> 记入未检验对偶数列表
//4> 判断该数是否是质数
//5> 如果不是,回到2>
//6> 如果是,记入已有质数表
//7> 检验对偶
//8> 检验成功,回到2>
//9> 检验失败,退出运行;
//判断某数是否质数
//1.取第2个已有质数(第1个是1,不用来检验)
//2.求本数与该质数的商余;
//3.如果商余不为0,不是质数退出。
//4.取下一个已有质数,回到2。
//5.取完所有已有质数,是质数返回。
//检验对偶质数:任意一个数n的前后D个数之内,必有1对质数。
//1.取之前未过检验的第一个数
//2.计算该数与本数距离;
//3.查看该数之前相同距离的数,
//4.如果不存在,检查失败返回。
//5.如果存在,检查该数是否已有质数之一
//6.如果是,则检验通过
//7.如果不是,检验不过
//8.取下一个之前未过检验的数,回到2.
//9.所有未检验数得到检验,成功返回。
unit UnitGedbahe;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, StdCtrls, ExtCtrls;
Type
TDispCtl = Record
PrimeNums : TStrings;
UnChkNums : TStrings;
StartBtn : TButton;
PanPrime : TPanel;
PanChk : TPanel;
end;
PPHashItem = ^PHashItem;
PHashItem = ^THashItem;
THashItem = record
Next: PHashItem;
Key: string;
Value: Integer;
end;
TPrimeNumHash = class(TObject)
private
Buckets: array of PHashItem;
protected
function Find(const Key: string): PPHashItem;
function HashOf(const Key: string): Cardinal; virtual;
public
constructor Create(Size: Cardinal = 256);
destructor Destroy; override;
procedure Add(Value: Integer);
procedure Clear;
function Exist(AValue: Integer): Boolean;
end;
PIntNum = ^TIntNum;
TIntNum = record
Value : Integer;
end;
TIntNumList = Class(TList)
Private
Protected
Function GetValue(AInt : Integer) : Integer;
Function GetIntNum(AInt : Integer) : PIntNum;
Public
Property Values[AInt: Integer] : Integer Read GetValue;
Property IntNum[AInt: Integer] : PIntNum Read GetintNum;
End;
TPrimeList = Class(TIntNumList)
Private
FPrimeNumHash : TPrimeNumHash;
Function AddIntNum(AIntNum : PIntNum) : Integer;
Procedure ClearIntNums;
Protected
Public
Constructor Create;
Destructor Destroy; Override;
Procedure RecordValue(AInt : PIntNum); //记入已有质数表
Function IsPrimeNum(AInt : PIntNum) : Boolean; //判断该数是否是质数
Function IsExistPrimeNum(AInt : Integer) : Boolean; //检查该数是否已有质数之一
End;
TUnCheckInts = Class(TIntNumList)
Private
Protected
Public
Function AddValue(AValue: Integer) : PIntNum;
End;
TProveThread = Class;
TProveOver = Procedure of Object;
TGedebahe = Class(TObject)
Private
FPrimeNums : TPrimeList;
FUnChkInts : TUnCheckInts;
FDispCtl : TDispCtl;
FProveThread : TProveThread;
FSetDelay : Boolean;
FDispPrime : Boolean;
FDispUnChk : Boolean;
FReqStop : Boolean;
FProveOver : TProveOver;
Procedure IniDatas;
Protected
procedure ThreadDone(Sender: TObject);
Public
Constructor Create(AList, Blist : TStrings; ABtn : TButton; Apan,BPan : TPanel);
Destructor Destroy; Override;
Procedure StartProve;
Procedure Pause;
Procedure Stop;
Procedure Continue;
Property PrimeNums : TPrimeList read FPrimeNums;
Property UnChkInts : TUnCheckInts read FUnChkInts;
Property DispCtl : TDispCtl Read FDispCtl;
Property SetDelay : Boolean Read FSetDelay Write FSetDelay;
Property DispPrime : Boolean Read FDispPrime Write FDispPrime;
Property DispUnChk : Boolean Read FDispUnChk Write FDispUnChk;
Property ReqStop : Boolean Read FReqStop Write FReqStop;
Property OnProveOver : TProveOver Read FProveOver Write FProveOver;
End;
TProveThread = class(TThread)
private
FN : String;
FID : Integer;
FGedebahe : TGedebahe;
procedure DoVisualSwapUnChkInts;
procedure DoVisualSwapRecPrime;
procedure DoVisualSwapRemoveUnChkInt;
Procedure Delay;
protected
procedure Execute; override;
procedure VisualSwapUnChkInts(n : Integer);
procedure VisualSwapRemoveUnChkInt(n : Integer);
procedure VisualSwapRecPrime(AInt : PIntNum);
procedure Prove;
Function IsPrimeNum(AInt : PIntNum) : Boolean;
Function ChkTwins(AInt : Integer) : Boolean;
public
constructor Create(AGedebahe : TGedebahe);
end;
...
修改了一下程序,添加显示检验结果,试验运行约4小时结果:
准备明早再看结果。
运行大约11小时后的结果:
下班回家再看程序,已经界面溢出错。应该在上次之后没有运行太久,程序需要再改进。
程序验证到4百多万大小的整数,列出了相应的质数表。
回头去掉界面显示表,可加快运行。看看我的电脑极限能运行到多大。
改进程序运行大约10小时后画面:
验证了8百多万个整数,速度提高大约3倍,界面显示不再有溢出机会。
再次改进后程序运行约12小时后界面截图。
完成到约2^24规模验证。速度是否提高,未知。
https://wap.sciencenet.cn/blog-33982-480594.html
上一篇:
一个表达式的用法问题下一篇:
如何与德高望重的前辈探讨问题而不伤和气