来点简单的，素性测试相关小问题

无心人

最近搞定了这个问题

无心人

Julia语言的源代码
求factors的那个利用了库，但是其实很简单，可以自己实现
因为，候选的素因子是很少的，比如，低于100
否则得到的结果，不是最佳的Jacobi sum的参数选择
按照Jacobi算法的要求，
\(  N = \prod p^{p_i} \enspace   S = 2 \prod_{q-1|N } q^{v_i}  \), p, q都是素数，且\(v_i\)满足如果\(q | N\), \(v_i = p_i + 1 \)否则\(v_i = 1\)

1. using Primes
   
2. using Printf
   
3. 
   
4. function allMul(x, y)
   
5.     [i * j
   
6.        for i in x
   
7.            for j in y]
   
8. end
   
9. 
   
10. function calc(n, factors)
    
11.     factorList = [1]
    
12.     primeList = []
    
13.     for (p, k) in factors
    
14.         numpower = [1]
    
15.         num = 1
    
16.         for i in 1:k
    
17.             num *= p
    
18.             push!(numpower, num)
    
19.         end
    
20.         factorList = allMul(factorList, numpower)
    
21.     end
    
22.     sort!(factorList)
    
23.     return factorList
    
24. end
    
25. 
    
26. function filterPrime(n, factors, factorList)
    
27.     k = factors[2]
    
28.     s = big(2)^big(k+2)
    
29.     primeList = [(2, k + 2)]
    
30.     for x in factorList
    
31.         z = x + 1
    
32.         if Primes.isprime(z) && (z > 2)
    
33.             k = factors[z]
    
34.             s *= big(z)^big(k + 1)
    
35.             push!(primeList, (z, k + 1))
    
36.         end
    
37.     end
    
38.     return log10(s), s, primeList
    
39. end
    
40. 
    
41. numbers = [
    
42. 210,420,840,1260,1680,2520,3360,3780,5040
    
43. ,7560,8400,10080,12600,15120,25200,30240,42840,45360,55440,60480,75600,85680,100800,110880,128520,131040,166320,
    
44. 196560,257040,332640,393120,514080,655200,665280,786240,831600,917280,982800,1081080,1179360,1285200,1310400,1441440,1663200,1965600,2162160,2751840,2827440,
    
45. 3326400,3341520,3603600,3931200,4324320,5654880,6652800,6683040,7207200,8648640,10810800,12972960,14414400,18378360,21621600,36756720,43243200,64864800,73513440,
    
46. 86486400,113097600,122522400,129729600,147026880,172972800,183783600,216216000,220540320,245044800,273873600,294053760,302702400,367567200,514594080,551350800,
    
47. 735134400,821620800,1029188160,1074427200,1102701600,1470268800,1643241600,2058376320,2148854400,2205403200,2572970400,2940537600,3491888400,3675672000,4108104000
    
48. ]
    
49. for n in numbers
    
50.     factors = Primes.factor(n)
    
51.     factorList = calc(n, factors)
    
52.     digits, s, primeList = filterPrime(n, factors, factorList)
    
53.     println(n, " factors = ", factors)
    
54.     println( " factorList = ", factorList)
    
55.     println("primes = ", primeList)
    
56.     println(" s = ", s)
    
57.     @printf(" digits = %.3f\n", digits)
    
58.     println("========================================================");
    
59. end
    

复制代码