数量较大的非唯一素数 [英] Non distinct prime factors of larger numbers

问题描述

我编写并使用此函数来生成数字的素因子:

I wrote and use this function to produce prime factors of a number:

import numpy as np
from math import sqrt

def primesfrom3to(n):
    """ Returns a array of primes, p < n """
    assert n>=2
    sieve = np.ones(n/2, dtype=np.bool)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = False
    return np.r_[2, 2*np.nonzero(sieve)[0][1::]+1]    

def primefactors(tgt,verbose=True):
    if verbose: 
        print '\n\nFinding prime factors of: {:,}'.format(tgt)

    primes=primesfrom3to(sqrt(tgt)+1)

    if verbose:
        print ('{:,} primes between 2 and square root of tgt ({:.4})'.
                      format(len(primes),sqrt(tgt))) 

    return [prime for prime in primes if not tgt%prime]

如果我使用欧拉工程#3 中的值调用此函数，它将成功生成不同素数的列表:

If I call this with the value from Project Euler #3, it successfully produces the list of distinct primes:

>>> print primefactors(600851475143)
Finding prime factors of: 600,851,475,143
62,113 primes between 2 and square root of tgt (7.751e+05)
[71, 839, 1471, 6857]

这与 Wolfram Alpha产生的主要因子一致. (最大的问题是对欧拉计划3的正确答案)

This agrees with what Wolfram Alpha produces for the prime factors. (And the largest there is the correct answer to Project Euler #3)

现在让我们说我想乘以这个数字x 1e6:

Now let's say that I want to factors of that number x 1e6:

>>> print primefactors(600851475143*1000000)
Finding prime factors of: 600,851,475,143,000,000
39,932,602 primes between 2 and square root of tgt (7.751e+08)
[2, 5, 71, 839, 1471, 6857]

对于更大的数字， Wolfram Alpha产生:

2**6 * 5**6 * 71 * 839 * 1471 * 6857

是否有一种简单的方法可以修改我的代码，使我可以计算2和5的大小，并将其作为较大数量的素数?

Is there an easy way to modify my code that I can calculate the magnitude of the 2 and the 5 as prime factors of the bigger number?

(我对其中的原始代码或算法很感兴趣-不是指向将为我做的图书馆的指针，谢谢！)

(I am interested in the raw code or algorithm of this -- not a pointer to a library that will do it for me, thanks!)

推荐答案

以这种方式，这很容易(而且更快，更高效):

Respectfully, this is easier (and a whole lot faster and more efficient) this way:

from collections import defaultdict
from math import sqrt

def factor(n):
    i = 2
    limit = sqrt(n)    
    while i <= limit:
      if n % i == 0:
        yield i
        n = n / i
        limit = sqrt(n)   
      else:
        i += 1
    if n > 1:
        yield n

def pfac(num):
    d=defaultdict(int)
    for f in factor(num):
        d[f]+=1

    terms=[]
    for e in sorted(d.keys()):
        if d[e]>1:
            terms.append('{:,}^{}'.format(e,d[e]))
        else:
            terms.append('{:,}'.format(e))

    print ' * '.join(terms),'=','{:,}'.format(num)           

pfac(600851475143*1000000-1)
pfac(600851475143*1000000)
pfac(600851475143*1000000+1)

打印:

83 * 127 * 57,001,373,222,939 = 600,851,475,142,999,999
2^6 * 5^6 * 71 * 839 * 1,471 * 6,857 = 600,851,475,143,000,000
3^2 * 19 * 103 * 197 * 277 * 16,111 * 38,803 = 600,851,475,143,000,001

这篇关于数量较大的非唯一素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！