파이썬 스크립트에 의한 Php 프라임 인수

Question

프라임 분해를 수행하는 python 스크립트가 있습니다. 매우 빠르며 1 초 이내에 실행됩니다. 그러나 매우 느리게 실행되는 php에 대한 일부 기능이 있습니다. 과 같은 하나의 매개 변수 (긴 정수)를 취하여 소수 분해를 계산합니다. 2 개의 인덱스를 가지는 배열을 돌려줍니다. 이 번호에 대한 결과는 다음과 같습니다

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

파이썬 스크립트 : (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() 

prime.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) 

것은 나도 몰라 파이썬 , 거기에 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); 
} 

Answer 1

이 있습니다. "프라임 분해"알고리즘을 연구해야합니다. 검색에 PHP를 추가하면 위의 brute-force 메소드보다 더 나은 구현을위한 코드를 찾을 수 있습니다. 시작 here. 파이썬 방법은 알고리즘에 대한 아무것도 표시되지 않습니다

는

참고 : 주요 패키지가 알고리즘을 내장하고, 당신이 준 코드는 단지 그것을 호출했다. 나는 파이썬 패키지가 확률 론적 방법을 사용한다는 것을 읽었다. (이것은 300 자리 숫자와 같은 것을 통해 100 % 정확함을 테스트했다.) 연구 할 때주의를 기울이십시오. 몇 가지 범용 언어로 구현할 수 있습니다. 최소한 Python, Java 및 C++에 대해 알고 있습니다.