正整数分解的自定义函数

incognito

m refers to the m^th prime above or below n.

banjinjiu

香川群子 发表于 2013-9-5 11:41
一共四个关于素数的自定义函数，整合到一起了：

excel怎么使用？新手咨询：比如“153”这个数，在excel怎么运行程序，分解质因数？

lee1892

incognito 发表于 2013-9-5 23:27
m refers to the m^th prime above or below n.

m是负的好说
正的嘛，即便是1，也不可能快速找到
不限定n的大小？

...
前面提到的2种素性测试，都是随机性测试，对于较大的质数能给出一个是否为质数的概率性结果，尽管结果非常准。

2005年有人发表了名为AKS的素性测试方法，确定的且不基于任何未证明的猜想，但慢一些。

香川群子

incognito 发表于 2013-9-5 23:27
m refers to the m^th prime above or below n.

返回距当前数的第k个素数。
k=0 时按k=1处理
k=1 时返回下一个素数
k=2 时返回第2个素数
……
k=-1 返回前一个素数
k=-2 返回前2个素数 → 到 1时终止。

1. Function NxtPrime&(ByVal n&, Optional k& = 1) '次の質数
   
2.     Dim b&, c&, f&
   
3.     On Error Resume Next
   
4.     If k < 0 Then f = -2 Else f = 2: If k = 0 Then k = 1
   
5.     If n Mod 2 = 0 Then NxtPrime = n - f / 2 Else NxtPrime = n
   
6.     b = 1
   
7.     Do
   
8.         NxtPrime = NxtPrime + f: n = NxtPrime: c = Int(n ^ 0.5)
   
9.         Do While b < c
   
10.             b = b + 2: If n Mod b = 0 Then b = 1: Exit Do
    
11.         Loop
    
12.         If b > 1 Then k = k - f / 2
    
13.     Loop Until k = 0 Or n < 3 '这里的容错处理比较复杂……略过了
    
14. End Function
    

复制代码

该函数表现不错，但对于n<3时也 一律返回5作为下一个素数。

即返回：  1、5、7、11……
而不是：  1、2、3、5、7、11…… 因为这部分的容错比较麻烦，忽略不搞了。

1        5        7        11        13        17        19
2        5        7        11        13        17        19
3        5        7        11        13        17        19
4        5        7        11        13        17        19
5        7        11        13        17        19        23
6        7        11        13        17        19        23
7        11        13        17        19        23        29
8        11        13        17        19        23        29
9        11        13        17        19        23        29
10        11        13        17        19        23        29


同样的，向下查找时也存在这个问题：
当前数        3        2        1        0        -1        -2        -3
1        9        7        5        5        -1        -1        -1
2        9        7        5        5        1        1        1
3        9        7        5        5        1        1        1
4        9        7        5        5        1        1        1
5        11        9        7        7        1        1        1
6        11        9        7        7        5        3        1
7        15        13        11        11        5        3        1
8        15        13        11        11        7        5        3
9        15        13        11        11        7        5        3
10        15        13        11        11        7        5        3


当前数        -1        -2        -3        -4        -5        -6        -7
1        -1        -3        -5        -7        -9        -11        -13
2        1        -1        -3        -5        -7        -9        -11
3        1        -1        -3        -5        -7        -9        -11
4        1        -1        -3        -5        -7        -9        -11
5        1        -1        -3        -5        -7        -9        -11
6        5        1        -1        -3        -5        -7        -9
7        5        1        -1        -3        -5        -7        -9
8        7        5        1        -1        -3        -5        -7
9        7        5        1        -1        -3        -5        -7
10        7        5        1        -1        -3        -5        -7

香川群子

重新优化了一下，改进如下：

1. Function NxtPrime(ByVal n&, Optional k& = 1) '次の質数
   
2.     Dim b&, c&, f&
   
3.     If k = 0 Then NxtPrime = IsPrime(Abs(n)): Exit Function '質数判断
   
4.     If k < 0 Then f = -2 Else f = 2
   
5.     NxtPrime = n - IIf(n Mod 2, 0, f / 2)
   
6.     Do
   
7.         NxtPrime = NxtPrime + f: n = Abs(NxtPrime)
   
8.         b = 1: c = Int(n ^ 0.5)
   
9.         Do While b < c
   
10.             b = b + 2: If n Mod b = 0 Then b = 0: Exit Do
    
11.         Loop
    
12.         If b Or n < 4 Then k = k - f / 2
    
13.     Loop Until k = 0
    
14. End Function
    
15. Function IsPrime$(ByVal n&) '質数判断
    
16.     If n < 4 Then IsPrime = "素数": Exit Function
    
17.     If n Mod 2 Then IsPrime = "素数" Else IsPrime = "合数": Exit Function
    
18.     b& = 1: m& = Int(n ^ 0.5)
    
19.     Do
    
20.         b = b + 2: If n Mod b = 0 Then IsPrime = "合数": Exit Function
    
21.     Loop While b < m
    
22. End Function

复制代码

k参数=0 时，判断当前数为素数或合数
【默认】k=1时，返回比当前数大的第1个素数
k=2 时，返回比当前数大的第2个素数
……
k=n 时，返回比当前数大的第n个素数

……
……
k=-1时，返回比当前数小的第1个素数
k=-2时，返回比当前数小的第2个素数
……
k=-n时，返回比当前数小的第n个素数


…………
返回的素数序列中，不包含偶数2，但包含1

incognito

n的大小，还是搂主决定为妥。

香川群子

incognito 发表于 2013-9-6 14:19
n的大小，还是搂主决定为妥。

在Excel VBA中，只能使用Long型整数，不超过 2^31-1=2147483647

incognito

In 1772, Leonhard Euler discoveried this mersenne number.

ydlpc

有意思，数学的魅力有时真的无法解释。

jinhaitiao16

我的第一反应是用字典，虽然笨，但易理解