数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
楼主: ysr

《数论探秘》电子版

  [复制链接]
 楼主| 发表于 2021-10-17 21:33 | 显示全部楼层
ysr 发表于 2021-10-17 13:12
超过传送容量了!分成两个图片来传,再传一个:

回复您的点评:
好的,谢谢沟通!程序能运行了,只是结果是否符合要求呢?我没有理解您的要求,输出结果中有的不是素数?
不知道结果对不对。

祝不断进步,早日熟悉掌握VB程序设计!
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-10-18 10:33 | 显示全部楼层
如下程序速度非常快,是高手做的程序,VB编程论坛高手回复了你的帖子。
程序运行结果:4457973个数无法表示为p+2^N的形式,用时20.8479999999981秒.
Msgbox上显示的是19.6秒,1亿内的奇数算完了,够快吧!

如下是代码:

Dim pri(100000000) As Byte, gusnum(10) As Long

Sub getpri()
  '获取一亿内素数map,5秒内可完成
  Dim i As Long, j As Long
  pri(0) = 1
  pri(1) = 1
  For i = 4 To 100000000 Step 2
    pri(i) = 1
  Next
  For i = 3 To 10000 Step 2
    If pri(i) = 0 Then
      For j = i * i To 100000000 Step i * 2
        pri(j) = 1
      Next
    End If
  Next
End Sub

Private Sub Command1_Click()
  '验证猜想,统计不符合的总数,并把前10个数存到数组中供验证
  Dim i As Long, j As Long, k As Long, t As Double
  t = Timer()
  For i = 5 To 100000000 Step 2
    j = 2
    Do While j < i
      If pri(i - j) = 0 Then Exit Do
      j = j * 2
    Loop
    If j >= i Then
      If k <= 10 Then gusnum(k) = i
      k = k + 1
    End If
  Next
  Text1 = k & "个数无法表示为p+2^N的形式,用时" & Timer() - t & "秒"
  MsgBox k & "个数无法表示为p+2^N的形式,用时" & Timer() - t & "秒"
End Sub

Private Sub Form_Load()
  getpri
  Command1_Click
End Sub

点评

多谢!ysr先生的大力帮助。  发表于 2021-10-18 10:51
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-10-18 10:36 | 显示全部楼层
本帖最后由 ysr 于 2021-10-18 02:49 编辑

4457973个数无法表示为p+2^N的形式,用时19.8479999999981秒(人家是5秒内就可以完成,我的电脑速度慢,需要20秒)
回复 支持 反对

使用道具 举报

发表于 2021-10-18 11:04 | 显示全部楼层
Dim pri(100000000) As Byte, gusnum(10) As Long

Sub getpri()
  '获取一亿内素数map,5秒内可完成
  Dim i As Long, j As Long
  pri(0) = 1
  pri(1) = 1
  For i = 4 To 100000000 Step 2
    pri(i) = 1
  Next
  For i = 3 To 10000 Step 2
    If pri(i) = 0 Then
      For j = i * i To 100000000 Step i * 2
        pri(j) = 1
      Next
    End If
  Next
End Sub

Private Sub Command1_Click()
  '验证猜想,统计不符合的总数,并把前10个数存到数组中供验证
  Dim i As Long, j As Long, k As Long, t As Double
  t = Timer()
  For i = 5 To 100000000 Step 2
    j = 2
    Do While j < i
      If pri(i - j) = 0 Then Exit Do
      j = j * 2
    Loop
    If j >= i Then
      If k <= 10 Then gusnum(k) = i
      k = k + 1
    End If
  Next
  MsgBox k & "个数无法表示为p+2^N的形式,用时" & Timer() - t & "秒"
End Sub

Private Sub Form_Load()
  getpri
  Command1_Click
End Sub
ysr先生有空把这个算法思路给介绍一下。
回复 支持 反对

使用道具 举报

发表于 2021-10-18 11:37 | 显示全部楼层
独木星空谁 发表于 2021-10-18 11:04
Dim pri(100000000) As Byte, gusnum(10) As Long

Sub getpri()

基本方法还是划线删除法。声明一个数组,递增依据,跳出依据,返回下一个依据。用个对话框报出不能表示的奇数量。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-10-18 11:59 | 显示全部楼层
本帖最后由 ysr 于 2021-10-18 04:00 编辑
独木星空谁 发表于 2021-10-18 03:04
Dim pri(100000000) As Byte, gusnum(10) As Long

Sub getpri()


这个算法的思路关键是筛法,就是在5秒内就可以产生1亿内的素数表。
用的就是筛法,是批量产生素数的,不是单个判断的,其他和你的程序的思路是一样的。

筛法就是,先把2的倍数删掉,在2的平方内就产生了3,再删掉3的倍数,在3的平方内就产生了5,7,等等,这样的速度快,占用内存,1亿内的数都要列出来,就是都要存起来,因此占用内存,最大可以把20亿内的素数筛选出来,普通电脑内存不够,最大算到20亿内。

大致是这样,具体做法请参考代码。

点评

对!批量生产,远远大于一个一个的生产,一个一个如手工,批量生产,就成了现代化的生产车间了,孰优孰劣,立判。  发表于 2021-10-18 17:52
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-10-18 12:51 | 显示全部楼层
存在任意多长的等差数列,其中的各项都是素数,这是个定理,据说陶哲轩已经证明了,咱没有见到,可能也看不懂。
其实,这个容易证明的,就是用初等数学知识就可以。下面发一下我的证明。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-10-18 13:36 | 显示全部楼层
本帖最后由 ysr 于 2021-10-18 05:46 编辑

二生素数对产生的必要条件也是这样:只要存在大于2的相邻素数的差(或者相邻素因子的差)就必然产生差为2m的素数对。

这个容易证明:
证明:

如下数列:

                    3,5,7,……
2m+2n+1:3+2m,5+2m,7+2m,……

对应项差为2m,若下排中的相邻素数p2-p1>=4,则在p2的下一个周期必然有3p2出现,就是3和p2必然重复占位,这就空缺一个位置,就是对应项不能被素因子占位的位置,就必然产生一对差为2m的素数对,必要条件得证!

例11-7=4>2,在11的下一个周期的33就是3和11重复占位,在13~33之间,13和7就是差为6的素数对,29和23也是差为6的素数对而且是相邻素数对。
而要产生4生素数组呢?必要条件就是存在大于等于6的相邻素数差。
这都是基础理论,基本规律,证明不复杂。书中没有证明,只是指出是必要条件 ,只要满足条件就可以产生4生素数组,当然还有个充分条件,对于由两对孪生素数组成的4生素数组,差依次为2,4,2就是充分条件,书中已经给出了证明。其它类型的4生素数组的充分条件道是没有指出来,仅仅指出并证明了由两对孪生素数对组成的4生素数组的充分条件,就是差依次为2,6m+4,2。已经证明了。

递推下去,2m生素数组的产生的原因呢?那就是存在大于等于2m+2的相邻素数的差,因为素数是越来越稀的,某数内的最大间距是个增函数,可以增长到无穷大的,无穷大于等于2m+2的相邻素数的差是存在的,则2m生素数组是存在的,其中的特例是:存在任意长的素数组,构成等差数列,这个被陶哲轩证明了据说,咱没见过人家的证明。

k生素数组的充分条件一般不好找,咱也不去找和证明了,肯定也是存在的,其实就是一句话:存在这样的k个数列其对应项任意两个都不能同时能被某素数整除,说的容易,找出来难。但肯定也是存在的,全体素数就构成了最大的一组k生素数组,这个存在性何需证明?

k生素数组产生的必要条件是容易证明的,不过没有必要证明了。任意长的等差数列其中都是素数的,就是一种k生素数,是特例,这个容易证明的。充分条件就是:公差为含有2,3,5,7,11,……,的多种不同的素因子,另一个是有k个数列,对应项依次相差都是2m。必要条件就是:存在大于等于数列项数+2的差的相邻素数。由于素数越来越稀,肯定存在这么大的相邻素数,所以,存在任意长的素数组成的等差数列,是必然的肯定的。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-10-18 15:40 | 显示全部楼层
今天医院床位满了,让我明天去住院做手术取钢板。
发个连乘积:2*3*5*7*11*……*97=2305567963945518424753102147331756070
虽然不大,手工计算就费力了,这是程序算的。
2*3*5*7*……*997=19590340644999083431262508198206381046123972390589368223882605328968666316379870661851951648789482321596229559115436019149189529725215266728292282990852649023362731392404017939142010958261393634959471483757196721672243410067118516227661133135192488848989914892157188308679896875137439519338903968094905549750386407106033836586660683539201011635917900039904495065203299749542985993134669814805318474080581207891125910(共有168个因子)
回复 支持 反对

使用道具 举报

发表于 2021-10-18 15:58 | 显示全部楼层
ysr 发表于 2021-10-18 15:40
今天医院床位满了,让我明天去住院做手术取钢板。
发个连乘积:2*3*5*7*11*……*97=230556796394551842475 ...

祝您手术顺利,早日健康!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 19:46 , Processed in 0.078125 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表