信息化的本质分享 http://blog.sciencenet.cn/u/Babituo

博文

歌德巴赫猜想自动枚举证明机程序

已有 6898 次阅读 2011-8-28 22:49 |个人分类:数据可视化|系统分类:论文交流| 程序

枚举原理:对偶质数原理。
歌德巴赫猜想是要证明:大于4的偶数可以写成两个质数的和。
可转化为:对任意一个整数存在一对与该整数前后距离相等的两个质数。
即:对于任意n,存在d,使得 n + d ,n - d 为质数。其中:d < n
 
程序使用多线程编写。
程序不出错自动停机则表示:歌德巴赫猜想不成立——我们要有耐心等程序运行
程序不停机:歌德巴赫猜想成立——可能等来的是溢出错误;
 
意义:
理解歌德巴赫猜想问题;
科学计算问题面向对象程序设计示范;
 
运行界面如下:
 
Delphi 7 源程序如下(包含执行程序):

ChkInt.rar

节选源码:
//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

上一篇:一个表达式的用法问题
下一篇:如何与德高望重的前辈探讨问题而不伤和气

3 田灿荣 宋敦江 cuiyujun

该博文允许注册用户评论 请点击登录 评论 (65 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-7-26 13:50

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部