正整数分解的自定义函数

香川群子

要求是：
【任意一个正整数，分解为质数的幂乘积】

举例：
111=3*37
53136=2^4*3^4*41
65536=2^16
1234567=127*9721
987654321=3^2*17^2*379721
987654323=987654323 (质数无法分解)


首先是分解为质数的连乘积：

1. 
   
2. Function f$(ByVal n&)
   
3.     Dim b&
   
4.     Do Until n < b ^ 2
   
5.         b = b + IIf(b = 2, 1, 2)
   
6.         Do
   
7.             If n Mod b Then Exit Do Else n = n / b: f = f & "*" & b
   
8.         Loop
   
9.     Loop
   
10.     If f = "" Then f = "=" & n Else f = "=" & Mid(f, 2) & IIf(n = 1, "", "*" & n)
    
11. End Function

复制代码

下面是分解为质数的幂乘积的自定义函数：

1. 
   
2. Function f$(ByVal n&)
   
3.     Dim b&, p&
   
4.     Do Until n < b ^ 2
   
5.         b = b + IIf(b = 2, 1, 2)
   
6.         Do
   
7.             If n Mod b Then
   
8.                 If p Then f = f & "*" & b & IIf(p = 1, "", "^" & p): p = 0
   
9.                 Exit Do
   
10.             Else
    
11.                 n = n / b: p = p + 1
    
12.             End If
    
13.         Loop
    
14.     Loop   
    
15.     If f = "" Then f = "=" & n Else f = "=" & Mid(f, 2) & IIf(n = 1, "", "*" & n)
    
16. End Function

复制代码

小花鹿

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

amesman

香川同学是搞什么的？数学老师吗？

lee1892

楼主写一个IsPrime(nNum@)的函数吧～

香川群子

lee1892 发表于 2013-9-4 23:23
楼主写一个IsPrime(nNum@)的函数吧～

如果对一个正整数n，仅需要做是否素数/质数的判断，代码几是一样的。
但对于合数Do循环将更快终止，计算反而更快更简单：

1. Function fs$(ByVal n&)
   
2.     If n < 4 Then fs = "素数": Exit Function
   
3.     If n Mod 2 Then fs = "素数" Else fs = "合数": Exit Function
   
4.     b& = 1: m& = Int(n ^ 0.5)
   
5.     Do
   
6.         b = b + 2: If n Mod b = 0 Then fs = "合数": Exit Function
   
7.     Loop While b < m
   
8. End Function

复制代码

香川群子

再增加一个函数，返回当前数的下一个素数。

1. Function f&(ByVal n&) 'NextPrime
   
2.     Dim b&, c&
   
3.     If n Mod 2 = 0 Then f = n - 1 Else f = n
   
4.     b = 1
   
5.     Do
   
6.         f = f + 2: n = f: c = Int(n ^ 0.5)
   
7.         Do
   
8.             b = b + 2: If n Mod b = 0 Then b = 1: Exit Do
   
9.         Loop While b < c
   
10.     Loop While b = 1
    
11. End Function

复制代码

Number	素数判断	下個素数	素数分解
1	素数	5	=1
2	素数	5	=2
3	素数	5	=3
4	合数	5	=2^2
5	素数	7	=5
6	合数	7	=2*3
7	素数	11	=7
8	合数	11	=2^3
9	合数	11	=3^2
10	合数	11	=2*5
11	素数	13	=11
12	合数	13	=2^2*3
13	素数	17	=13
14	合数	17	=2*7
15	合数	17	=3*5
16	合数	17	=2^4
17	素数	19	=17
18	合数	19	=2*3^2
19	素数	23	=19
20	合数	23	=2^2*5
21	合数	23	=3*7
22	合数	23	=2*11
23	素数	29	=23
24	合数	29	=2^3*3
25	合数	29	=5^2
26	合数	29	=2*13
27	合数	29	=3^3
28	合数	29	=2^2*7
29	素数	31	=29
30	合数	31	=2*3*5
31	素数	37	=31

lee1892

裙子小姐啊，再多看看吧

质数判断有很成熟的快速测试，必学的~
费马素性测试 Fermet's Primality Test
米勒-拉宾素性测试 Miller-Rabin Primality Test

至于质因数分解，则通常的做法是先生成所需要的全部质数，再逐个测试。
至于生成全部质数，有个很朴素的方法叫筛选法。

嗯嗯，还是多看看多学学~

香川群子

一共四个关于素数的自定义函数，整合到一起了：

1. Function myPrime(ByVal Num, Optional k = 0) '素数字
   
2.     'Max=2^31-1=2147483647
   
3.       If k = 0 Then myPrime = IsPrime(Num) '質素数/合数判断
   
4.     If k = -1 Then myPrime = PrimePower(Num)  '素因数の冪分解
   
5.     If k = -2 Then myPrime = PrimeProduct(Num)  '素因数の乗数分解
   
6.     If k = 1 Then myPrime = NxtPrime(Num)  '次の素数字
   
7. End Function
   
8. 
   
9. Function PrimePower$(ByVal n&) '質因数分解1　冪分解
   
10.     Dim b&, p&
    
11.     Do Until n < b ^ 2
    
12.         b = b + IIf(b = 2, 1, 2)
    
13.         Do
    
14.             If n Mod b Then
    
15.                 If p Then PrimePower = PrimePower & "*" & b & IIf(p = 1, "", "^" & p): p = 0
    
16.                 Exit Do
    
17.             Else
    
18.                 n = n / b: p = p + 1
    
19.             End If
    
20.         Loop
    
21.     Loop
    
22.     If PrimePower = "" Then PrimePower = "=" & n Else PrimePower = "=" & Mid(PrimePower, 2) & IIf(n = 1, "", "*" & n)
    
23. End Function
    
24. 
    
25. Function PrimeProduct$(ByVal n&) '質因数分解2　乗数分解
    
26.     Dim b&
    
27.     Do Until n < b ^ 2
    
28.         b = b + IIf(b = 2, 1, 2)
    
29.         Do
    
30.             If n Mod b Then Exit Do Else n = n / b: PrimeProduct = PrimeProduct & "*" & b
    
31.         Loop
    
32.     Loop
    
33.     If PrimeProduct = "" Then PrimeProduct = "=" & n Else PrimeProduct = "=" & Mid(PrimeProduct, 2) & IIf(n = 1, "", "*" & n)
    
34. End Function
    
35. 
    
36. Function IsPrime$(ByVal n&) '質数判断
    
37.    If n < 4 Then IsPrime = "素数": Exit Function
    
38.     If n Mod 2 Then IsPrime = "素数" Else IsPrime = "合数": Exit Function
    
39.     b& = 1: m& = Int(n ^ 0.5)
    
40.     Do
    
41.         b = b + 2: If n Mod b = 0 Then IsPrime = "合数": Exit Function
    
42.     Loop While b < m
    
43. End Function
    
44. 
    
45. Function NxtPrime&(ByVal n&) '次の質数
    
46.     Dim b&, c&
    
47.     If n Mod 2 = 0 Then NxtPrime = n - 1 Else NxtPrime = n
    
48.     b = 1
    
49.     Do
    
50.         NxtPrime = NxtPrime + 2: n = NxtPrime: c = Int(n ^ 0.5)
    
51.         Do
    
52.             b = b + 2: If n Mod b = 0 Then b = 1: Exit Do
    
53.         Loop While b < c
    
54.     Loop While b = 1
    
55. End Function
    

复制代码

香川群子

lee1892 发表于 2013-9-5 11:33
裙子小姐啊，再多看看吧

质数判断有很成熟的快速测试，必学的~

本帖的VBA代码，不做数学研究。

并且由于 Mod函数 只允许使用Long 数值最大 2^31-1=2,147,483,647

……

所以你说的那些“高级”算法无需考虑。

老谭酸菜

有办法证明以下结论吗？
（1）2和3是所有素数中唯一两个连着的数。
（2）2是唯一一个为偶数（双数）的质数。