gpt4 book ai didi

通过python脚本进行Php质因数分解

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:15:12 33 4
gpt4 key购买 nike

有一个 python 脚本可以进行质因数分解。它非常快,不到一秒即可运行。但是 php 的一些函数运行起来很慢。它采用一个参数(一个长整型),例如 1278426847636566097 并计算质因数分解。返回具有 2 个索引的数组。这个数字的结果是:

Array ( [0] => 1233387599 [1] => 1036516703 )

python 脚本: (getpq.py)

#!/usr/bin/env python
from __future__ import print_function
import prime
import sys
import json

def eprint(*args, **kwargs):
print(*args, file=sys.stderr, **kwargs)


pq = prime.primefactors(long(sys.argv[1]))

sys.stdout.write(json.dumps(pq))
sys.stdout.flush()

主要.py:

# NOTICE!!! This is copied from https://stackoverflow.com/questions/4643647/fast-prime-factorization-module

import random

def primesbelow(N):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
#""" Input N>=6, Returns a list of primes, 2 <= p < N """
correction = N % 6 > 1
N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
sieve = [True] * (N // 3)
sieve[0] = False
for i in range(int(N ** .5) // 3 + 1):
if sieve[i]:
k = (3 * i + 1) | 1
sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

smallprimeset = set(primesbelow(100000))
_smallprimeset = 100000

def isprime(n, precision=7):
# http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
if n == 1 or n % 2 == 0:
return False
elif n < 1:
raise ValueError("Out of bounds, first argument must be > 0")
elif n < _smallprimeset:
return n in smallprimeset


d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1

for repeat in range(precision):
a = random.randrange(2, n - 2)
x = pow(a, d, n)

if x == 1 or x == n - 1: continue

for r in range(s - 1):
x = pow(x, 2, n)
if x == 1: return False
if x == n - 1: break
else: return False

return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
def pollard_brent(n):
if n % 2 == 0: return 2
if n % 3 == 0: return 3

y, c, m = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1)

g, r, q = 1, 1, 1
while g == 1:
x = y
for i in range(r):
y = (pow(y, 2, n) + c) % n

k = 0
while k < r and g==1:
ys = y
for i in range(min(m, r-k)):
y = (pow(y, 2, n) + c) % n
q = q * abs(x-y) % n

g = gcd(q, n)
k += m
r *= 2
if g == n:
while True:
ys = (pow(ys, 2, n) + c) % n
g = gcd(abs(x - ys), n)
if g > 1:
break

return g

smallprimes = primesbelow(10000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000
def primefactors(n, sort=False):
factors = []

limit = int(n ** .5) + 1
for checker in smallprimes:
if checker > limit: break
while n % checker == 0:
factors.append(checker)
n //= checker
limit = int(n ** .5) + 1
if checker > limit: break

if n < 2: return factors

while n > 1:
if isprime(n):
factors.append(n)
break
factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent
factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent
n //= factor

if sort: factors.sort()

return factors

def factorization(n):
factors = {}
for p1 in primefactors(n):
try:
factors[p1] += 1
except KeyError:
factors[p1] = 1
return factors

totients = {}
def totient(n):
if n == 0: return 1

try: return totients[n]
except KeyError: pass

tot = 1
for p, exp in factorization(n).items():
tot *= (p - 1) * p ** (exp - 1)

totients[n] = tot
return tot

def gcd(a, b):
if a == b: return a
while b > 0: a, b = b, a % b
return a

def lcm(a, b):
return abs(a * b) // gcd(a, b)

因为我不懂 python,有什么办法可以做到这一点是 php 吗?

注意:我发现一个非常糟糕的算法,用 php 实现,大约需要 600 秒:

public function primefactor($num) {
$sqrt = sqrt($num);
for ($i = 2; $i <= $sqrt; $i++) {
if ($num % $i == 0) {
return array_merge($this->primefactor($num/$i), array($i));
}
}
return array($num);
}

最佳答案

当然有。您需要研究“质因数分解”算法。如果您将 PHP 作为搜索的要求添加,您可以找到比上面的暴力方法更好的实现代码。开始here .

请注意,Python 方法不显示有关算法的任何内容:prime 包具有内置算法,您提供的代码只是调用它。我读过 Python 包使用概率方法(通过 300 位数字之类的东西测试为 100% 准确)。当你做你的研究时,请留意那些。将有几种通用语言的实现;我至少知道 Python、Java 和 C++。

关于通过python脚本进行Php质因数分解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42057031/

33 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com