Python : 素数

Question

给定一个正数 n > 1 求 n 的质因数分解。结果将是具有以下形式的字符串：

"(p1**n1)(p2**n2)...(pk**nk)"

p(i) 递增，如果 n(i) 为 1，则 n(i) 为空。

示例：n = 86240 应该 return "(2**5)(5)(7**2)(11)"

这是我的代码，但我对 n>250000

的时间有疑问

def primeFactors(n):
    a=""
    i=2
    while i<=n:
        #part of identifying if number i is prime
        w1=5
        w2=2
        gg=0
        while w1*w1<=i:
            if i%w1==0:
                gg=1
                break
            w1+=w2
            w2=6-w2
        #checking if previous loop has been broken
         if gg:
            i+=1
            continue
        #countig how many thimes we can divide n on i
        c=0
        for j in range(1,n):
            if n%i!=0: break
            c+=1
            n=n//i
        #if we can divide n on i only once
        if c==1:
            a+="("+str(i)+")"
        elif c>1:
            a+="("+str(i)+"**"+str(c)+")"
        i+=1
    return a

有办法解决这个问题吗？

Answer 1

问题不在于程序所做的质因数分解，而是 Python 在非常短的时间内对非常大的数字进行分解。具体来说，我的理解是我们需要能够计算：

for n in range(10 ** 9, 10 ** 9 + 10):
    print(n, '=', primeFactors(n))

in <= 120ms 或更少，即每个数字 <= 12ms。在毫秒变成秒、秒变成分钟之前，OP 的代码不会超过 10 ** 9 + 4。我对您的代码的第一印象是您需要将主要逻辑与其余代码分开，使其易于理解，然后清理和优化代码的这两部分。我重写了你的程序：

def generate_primes(n):

    """ generate real primes """

    yield(2)

    primes = [(2, 4)]

    for m in range(3, n, 2):

        for prime, square in primes:

            if square > m:
                yield(m)
                primes.append((m, m * m))
                break

            if m % prime == 0:
                break

def primeFactors(n):
    string = ""
    i = 2

    for i in generate_primes(int(n ** 0.5) + 1):

        # counting how many times we can divide n on i
        c = 0

        while True:
            product, remainder = divmod(n, i)

            if remainder != 0:
                break

            n = product
            c += 1

        # if we can divide n on i only once
        if c == 1:
            string += f"({i})"
        elif c > 1:
            string += f"({i}**{c})"

    if n > 1:  # final prime factor greater than square root
        string += f"({n})"

    return string

我换了一个质数生成器以避免冗余计算。在上述测试中，此优化版本可以实现每个大数分解 32 毫秒。还是不够好。所以让我们试试@JamesKPolk 的建议并使用伪素数：

def generate_primes(n):

    """ generate 5-rough pseudoprimes """

    if n >= 2:
        yield(2)

    if n >= 3:
        yield(3)

    if n >= 5:
        m = 1
        x = 4

        while m < n:
            m += x
            yield(m)
            x = 6 - x

这里的权衡是我们将测试比实际需要更多的除数，但我们可以更快地生成这些除数。无论如何，在我的机器上，此更改实现了我们的目标，即 <= 12ms 每个大数因式分解。

输出

> time python3 test.py
1000000000 = (2**9)(5**9)
1000000001 = (7)(11)(13)(19)(52579)
1000000002 = (2)(3)(43)(983)(3943)
1000000003 = (23)(307)(141623)
1000000004 = (2**2)(41**2)(148721)
1000000005 = (3)(5)(66666667)
1000000006 = (2)(500000003)
1000000007 = (1000000007)
1000000008 = (2**3)(3**2)(7)(109**2)(167)
1000000009 = (1000000009)
0.106u 0.010s 0:00.11 100.0%    0+0k 0+0io 0pf+0w
>

Python : 素数

Python : Primes in numbers

python

primes

python-3.x