擂台第36期投票

redraiment

code

xmxoxo

Option Explicit

Public lngTime As Long

'计算上限
Public lngLength As Long

'数表
Public lngTable() As Byte

'结果数组
Public lngRet() As Long

'结果个数
Public lngCount As Long

'筛数组

'被删除的合数个数
Public lngDel As Long
Public Declare Function timeGetTime Lib "winmm.dll" () As Long


'从表中划去素数的倍数
Public Sub DelFromTable(value As Long)
    Dim k As Long
    Dim i As Long
   
    '优化,从种子的平方开始,步长为素数2倍
    For i = value * value To lngLength Step value * 2
        If lngTable(i) = 0 Then
            lngDel = lngDel + 1     '记录删除掉的个数
            lngTable(i) = 1
        End If
    Next
End Sub



'筛选法,速度1亿=4250
Public Function GetPrime3()
    Dim i As Long
    Dim j As Long
    Dim blnFound As Boolean
    Dim lngPos As Long
   
    If lngLength < 4 Then
        Exit Function
    End If
   
    lngCount = 1
'    ReDim lngRet(0)
    ReDim lngTable(lngLength)

    '初始时2,3为已知素数
    lngTable(0) = 1
    lngTable(1) = 1
    lngDel = 0
   
    lngPos = Sqr(lngLength)
    For i = 3 To lngLength Step 2
        If lngTable(i) = 0 Then
            '找到一个素数,则加入到数组中
            
            '把素数的倍数从表中划去
            If i <= lngPos Then
                Call DelFromTable(i)
            Else
                Exit Do
            End If
        End If
    Loop
'    Debug.Print timeGetTime() - lngTime
'    Debug.Print "总数:" & lngLength & ",找到:" & lngCount & ",划去:" & lngDel & ",理论划去:" & lngLength / 2 - lngCount & ",超划:" & lngDel - (lngLength / 2 - lngCount)
    lngCount = lngLength / 2 - lngDel
    ReDim lngRet(lngCount - 1)
   
    j = 1
    lngRet(0) = 2

    For i = 3 To lngLength Step 2
        If lngTable(i) = 0 Then
            lngRet(j) = i
            j = j + 1
        End If
    Next
End Function

yidie

For i = 3 To lngLength Step 2
        If lngTable(i) = 0 Then
            '找到一个素数,则加入到数组中
            
            '把素数的倍数从表中划去
            If i <= lngPos Then
                Call DelFromTable(i)
            Else
                Exit Do   ????
            End If
        End If
    Loop   ??????

ymismy

33楼不要笑。
不过32楼的代码可以运行吗？可以达到 2983？

yidie

原帖由 ymismy 于 2007-8-1 16:15 发表
33楼不要笑。
不过32楼的代码可以运行吗？可以达到 2983？

我意思是32楼那代码不完整，运行会出错。

xmxoxo

不好意思，我还是打包吧。

xmxoxo

有点乱，本来想只贴出有用的代码，结果。。。。
还是打包上来，当时思路有点乱。

YaDa

我投 仙剑魔 他最快

ckz727

同上

cwa9958

下来学学算法哦，看看谁最快，再投票