用VBA解欧拉计划题目（51）

大灰狼1976

Problem 51 Prime digit replacements
通过置换*3的第一位得到的9个数中，有六个是质数：13,23,43,53，73和83。
通过用同样的数字置换56**3的第三位和第四位，这个五位数是第一个能够得到七个质数的数字，得到的质数是：56003, 56113, 56333, 56443, 56663, 56773, 和 56993。因此其中最小的56003就是具有这个性质的最小的质数。
找出最小的质数，通过用同样的数字置换其中的一部分（不一定是相邻的部分），能够得到八个质数。

grf1973

1. '素数数字替换
   
2. '
   
3. '将两位数*3的第一个数字代换为任意数字，在九个可能值中有六个是素数：13、23、43、53、73和83。
   
4. '
   
5. '将五位数56**3的第三和第四位数字代换为相同的任意数字，就得到了十个可能值中有七个是素数的最小例子，这个素数族是：56003、56113、56333、56443、56663、56773和56993。56003作为这一族中最小的成员，也是最小的满足这个性质的素数。
   
6. '
   
7. '通过将部分数字（不一定相邻）代换为相同的任意数字，有时能够得到八个素数，求满足这一性质的最小素数。
   
8. Sub problem51()   '结果是121313，需运行3.4秒
   
9.     tm = Timer
   
10.     n& = 1000000: Nmin = n / 10
    
11.     Set d = CreateObject("scripting.dictionary")
    
12.     arr = GetPrimeArray(n)   '得到100万以下的质数
    
13.     For i = 1 To UBound(arr)
    
14.         d(arr(i)) = ""
    
15.     Next
    
16.    
    
17.     For i = 1 To UBound(arr)
    
18.         If arr(i) > Nmin Then
    
19.             x = arr(i)         ' xstr = x
    
20.             If InStr(x, 0) Or InStr(x, 1) Or InStr(x, 2) Then
    
21.                 For k = 0 To 2
    
22.                     If InStr(x, k) Then
    
23.                         s = 1
    
24.                         For t = k + 1 To 9
    
25.                             y = Val(Replace(x, k, t))
    
26.                             If d.exists(y) Then s = s + 1   ' xstr = xstr & "," & y
    
27.                         Next
    
28.                         If s = 8 Then res = x: th = k: GoTo ext
    
29.                     End If
    
30.                 Next
    
31.             End If
    
32.         End If
    
33.     Next
    
34. ext:    Debug.Print s, res, "替换掉" & th, "共运行" & Timer - tm & "秒"      'smax, res
    
35. End Sub

复制代码

pengyx

1、不能置换最后一位数，2、被告置换的位数应该是3位或3的倍数位。

大灰狼1976

pengyx 发表于 2017-12-29 20:55
1、不能置换最后一位数，2、被告置换的位数应该是3位或3的倍数位。

总结得完全正确，还有一点可以剪枝，按顺序找到的第1个含有3个（或以上）重复数字的素数时，如果重复数字大于2，也不用往下判断了，直接找下一个。

大灰狼1976

长代码又发不上来了，用了下面最原始的判断素数法，时间0.4秒出结果。
Function jisuan(ByVal n)
For i = 3 To Sqr(n)
  If n Mod i = 0 Then jisuan = True: Exit For
  jisuan = False
Next i
End Function