高手编的快速计算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