高手编的快速计算16（1.6×10^9)亿内孪生素数的程序

ysr

Dim pri(200000000) As Byte

Sub Command1_Click()
  pritab
End Sub

Sub pritab()
  '用字节位筛法生成16亿以内的素数表
  Dim i As Long, j As Long, b(8) As Byte, c As Byte, k As Long, l As Long, t As Double
  j = 1
  t = Timer
  For i = 0 To 7
    b(i) = j
    j = j * 2       '位运算值初始化
  Next
  For i = 0 To 100020001
    pri(i) = 170    '先假设所有奇数都是素数
  Next
  pri(0) = 172      '0,1不是素数，2是素数
  i = 3
  While i * i <= 100020001
    If (pri(Int(i / 8)) And b(i Mod 8)) > 0 Then
      j = i * i
      While j <= 100020001
        If (pri(Int(j / 8)) And b(j Mod 8)) > 0 Then
          c = b(j Mod 8) Xor 255
          pri(Int(j / 8)) = pri(Int(j / 8)) And c
        End If
        j = j + i * 2
      Wend
    End If
    i = i + 2
  Wend
  k = 0
  j = 0
  For i = 2 To 100020001
    If (pri(Int(i / 8)) And b(i Mod 8)) > 0 Then
      If i - l = 2 And i >= 99980001 Then j = j + 1: Text1 = Text1 & l & "   " & i & vbCrLf
      k = k + 1
      l = i
    End If
  Next
  MsgBox "总素数：" & k & ",最大素数：" & l & "，99980001与100020001的孪生素数对：" & j & ",用时：" & Timer - t & "秒"
End Sub

ysr

这个程序的原理就是埃拉托尼筛，不用重复判断，可以批量产出素数！速度快但比较占用內充，数据太大的时候只能用巨型机了。

ysr

用埃拉托斯特尼筛法编的筛选素数的python程序（是可调用程序）：
def sieve_of_eratosthenes(n):
    # 初始化布尔数组，假设所有数都是素数
         sieve = [True] * (n + 1)  # 创建大小为 n+1 的布尔数组
         sieve[0] = sieve[1] = False  # 0 和 1 不是素数

    # 从 2 开始筛选
         for i in range(2, int(n ** 0.5) + 1):  # 只需到 sqrt(n)&#11088;转换为int类型
            if sieve[i]:  # 如果 i 是素数
                for j in range(i * i, n + 1, i):  # 将 i 的倍数标记为合数
                    sieve[j] = False
   
    # 返回所有值为 True 的索引，这些索引对应的数字是素数
         primes = [i for i in range(2, n + 1) if sieve[i]]
         return primes

ysr

调用前面的程序的可执行程序的代码：

print(sieve_of_eratosthenes(1000000))

ysr

Dim pri(200000000) As Byte

Sub Command1_Click()
  pritab
End Sub

Sub pritab()
  '用字节位筛法生成16亿以内的素数表
  Dim i As Long, j As Long, b(8) As Byte, c As Byte, k As Long, l As Long, t As Double
  j = 1
  t = Timer
  w = Val(Text1)
  For i = 0 To 7
    b(i) = j
    j = j * 2       '位运算值初始化
  Next
  For i = 0 To w
    pri(i) = 170    '先假设所有奇数都是素数
  Next
  pri(0) = 172      '0,1不是素数，2是素数
  i = 3
  While i * i <= w
    If (pri(Int(i / 8)) And b(i Mod 8)) > 0 Then
      j = i * i
      While j <= w
        If (pri(Int(j / 8)) And b(j Mod 8)) > 0 Then
          c = b(j Mod 8) Xor 255
          pri(Int(j / 8)) = pri(Int(j / 8)) And c
        End If
        j = j + i * 2
      Wend
    End If
    i = i + 2
  Wend
  k = 0
  j = 0
  For i = 2 To w
    If (pri(Int(i / 8)) And b(i Mod 8)) > 0 Then
      If i - l = 2 Then j = j + 1
      k = k + 1
      l = i
    End If
  Next
  MsgBox w & "内的总素数：" & k & ",最大素数：" & l & "，孪生素数对：" & j - 1 & ",用时：" & Timer - t & "秒"
End Sub

ysr

Dim pri(200000000) As Byte

Sub Command1_Click()
  pritab
End Sub

Sub pritab()
  '用字节位筛法生成16亿以内的素数表
  Dim i As Long, j As Long, b(8) As Byte, c As Byte, k As Long, l As Long, t As Double
  j = 1
  t = Timer
  w = Val(Text1)
  For i = 0 To 7
    b(i) = j
    j = j * 2       '位运算值初始化
  Next
  For i = 0 To w
    pri(i) = 170    '先假设所有奇数都是素数
  Next
  pri(0) = 172      '0,1不是素数，2是素数
  i = 3
  While i * i <= w
    If (pri(Int(i / 8)) And b(i Mod 8)) > 0 Then
      j = i * i
      While j <= w
        If (pri(Int(j / 8)) And b(j Mod 8)) > 0 Then
          c = b(j Mod 8) Xor 255
          pri(Int(j / 8)) = pri(Int(j / 8)) And c
        End If
        j = j + i * 2
      Wend
    End If
    i = i + 2
  Wend
  k = 0
  j = 0
  For i = 2 To w
    If (pri(Int(i / 8)) And b(i Mod 8)) > 0 Then
      If i - l = 2 Then j = j + 1
      k = k + 1
      l = i
    End If
  Next
  Text2 = w & "内的总素数：" & k & ",最大素数：" & l & "，孪生素数对：" & j - 1 & ",用时：" & Timer - t & "秒"
End Sub

ysr

勿忘国耻 ，强我中华！

ysr

最新版数论探秘的目录：
第一章  孪生素数猜想和哥德巴赫猜想的初等证明
第一节  几个概念......................................................1
第二节  孪生素数猜想的证明和哥德巴赫猜想的证明..........................3
第三节  抛物线数列中的孪生素数对和相邻素数对的差的定理..................6
第四节  孪生素数对总个数及其分布规律....................................10
第五节  差为2,4,6,8，……的相邻素数对是无穷多的........................12
第六节  抛物线数列中素因子的周期性和同一周期中的对称性.................12
第二章  哥德巴赫猜想成立的必要条件和充分条件
第一节  哥德巴赫猜想成立的条件.........................................13
第二节  哥德巴赫猜想解的个数的绝对下限.................................14
第三节  偶数哥德巴赫猜想解中的最小素数的求证...........................24
第四节  偶数的哥猜拆分素数和对的下限公式及程序等.......................29
第三章  素数分布规律和哥德巴赫猜想的验证
第一节  素数的分布规律.................................................30
第二节  哥德巴赫猜想的验证.............................................32
第三节  某数内相邻素数的最大间距的公式及推导...........................33
第四章  研究素数的几个常用公式
第一节  几个常用公式...................................................37
第二节  我证明的定理...................................................39
第三节  关于素数对个数的几个命题.......................................40
第四节  关于精确的素数个数公式和素数对个数公式及哥德巴赫猜想解个数公式的
推导和探索.....................................................41
第五节  差为2m的素数对个数的比例以及特殊K生素数探索……………………48
第五章  费尔马大定理的初等证明
第一节  费尔马大定理的初等证明.........................................49
第二节  证明a^(2/3),b^(2/3),c^(2/3)之中(abc为勾股数)必有1个无理数....69
第三节  勾股小题（1）..................................................72
第四节  勾股小题（2）..................................................72
第六章  知识储备
第一节  费尔马小定理.........................................74
第二节  欧拉原理等...........................................74
第三节  中国剩余定理和求乘法的逆元...........................75
第七章  知识扩展
第一节  傅立叶变换与大整数的快速计算.........................81
第二节  朋友的一元三次方程根式解的研究.......................88
第三节  RSA密码体制及大整数的快速分解和快速素性测试.........90
第四节  梅森素数和费马数的密码特性等.........................95
第五节  李明波孪中猜想的证明.................................97
第八章  几个趣味问题
第一节  素数小题.............................................108
第二节  电话号码问题.........................................109
第三节  传令兵走多远等....................................... 109
第四节  勾股定理的平民证法....................................114
后记.............................................................117
附录1，素数表.....................................................119
附录2，两个可调用程序............................................127
附录3，李明波给美国人的挑战书.....................................132
个人简介.........................................................133

ysr

ysr 发表于 2025-6-27 08:48
Dim pri(200000000) As Byte

Sub 按钮1_Click()

“时空伴随者:
最后一个循环，l应该赋初值，或者i从3开始，避免隐含的边界错误。  ”

您是对的，高手编的程序我没有弄清楚原理(据说就是艾拉托尼筛法，效率高些)，不敢改变初值，怕原理失效了，我也发现多了一对:0和2，输出的时候去掉 这对，总个数减1而已，所以，没有改变初值。