hiệu quả tạo ra tất cả hợp số ít hơn N (với factorizations của họ)

Question

Tôi muốn xây dựng một iterator Python hiệu quả/máy phát điện mà sản lượng:

• Tất cả các hợp số ít hơn N
• Cùng với chính của họ thừa số

tôi sẽ gọi nó là "composites_with_factors()"

Giả sử chúng ta đã có một li st của số nguyên tố nhỏ hơn N hoặc bộ tạo số nguyên tố có thể thực hiện tương tự.

Lưu ý rằng I:

• KHÔNG cần các con số để được mang lại theo số thứ tự
• KHÔNG quan tâm nếu 1 được mang lại ngay từ đầu hay không
• KHÔNG quan tâm nếu số nguyên tố được mang lại , quá

tôi con số này có thể được thực hiện với một máy phát điện đệ quy thông minh ...

Vì vậy, ví dụ, một cuộc gọi đến composites_with_factors (16) có thể mang lại:

# yields values in form of "composite_value, (factor_tuple)" 
2, (2) 
4, (2, 2) 
8, (2, 2, 2) 
6, (2, 3) 
12, (2, 2, 3) 
10, (2, 5) 
14, (2, 7) 
3, (3) 
9, (3, 3) 
15, (3, 5) 
5, (5) 
7, (7) 
11, (11) 
13, (13) 

Như bạn có thể nhìn thấy từ thứ tự của đầu ra của tôi, tôi nhận thức của công tác này bằng cách bắt đầu với thủ nhỏ nhất trên các máy phát điện số nguyên tố có sẵn, và xuất tất cả sức mạnh của số nguyên tố đó nhỏ hơn N, sau đó thử lại thông qua các lũy thừa của số nguyên tố đó nhưng ở mỗi giai đoạn sẽ thấy nếu tôi có thể áp dụng các lũy thừa bổ sung (và vẫn nhỏ hơn N). Khi tất cả các kết hợp với THAT chính được thực hiện, hãy thả nó và lặp lại với số nguyên tố thấp nhất tiếp theo có sẵn trên trình tạo số nguyên tố.

Nỗ lực của tôi để làm điều này với "máy phát đệ quy" đã khiến tôi rất bối rối khi bật ra khỏi đệ quy với "hiệu suất" hoặc "tăng Dừng lại" hoặc "trả lại" hoặc đơn giản rơi ra khỏi chức năng.

Cảm ơn sự thông thái của bạn!

BỔ SUNG LƯU Ý:

tôi làm có một cách để làm điều này ngay bây giờ: Tôi đã viết một hàm đến yếu tố con số, vì vậy tôi có thể yếu tố chúng xuống số nguyên tố, và mang lại kết quả. Không vấn đề gì. Tôi giữ điều này một cách nhanh chóng bằng cách dựa vào bộ đệm "yếu tố chính thấp nhất của số N" ... cho N lên tới 10 triệu.

Tuy nhiên, một khi tôi đã thoát khỏi bộ nhớ cache, chúng tôi sẽ, nó sẽ biến thành sự thừa nhận "ngây thơ". (. Yuck)

Mục đích của bài này là:

• Tôi giả định rằng "tạo composit lớn từ các yếu tố của họ" sẽ nhanh hơn "Sacombank composit lớn" ... đặc biệt là kể từ khi tôi DON 'T quan tâm đến trật tự, và
• Làm cách nào để bạn có thể tạo một trình tạo Python "gọi đệ quy" và tạo ra một luồng các thứ được tạo ra?

Answer 1

Giả sử primesiter(n) tạo ra một iterator khắp các số nguyên tố lên đến n (1 KHÔNG cần được đưa vào primesiter, hoặc mã sau cũng nhập inf vòng lặp.)

def composite_value(n, min_p = 0): 
    for p in primesiter(n): 
     # avoid double solutions such as (6, [2,3]), and (6, [3,2]) 
     if p < min_p: continue 
     yield (p, [p]) 
     for t, r in composite_value(n//p, min_p = p): # uses integer division 
      yield (t*p, [p] + r) 

Output

>> list(composite_value(16)) 
[(2, [2]), 
(4, [2, 2]), 
(8, [2, 2, 2]), 
(16, [2, 2, 2, 2]), 
(12, [2, 2, 3]), 
(6, [2, 3]), 
(10, [2, 5]), 
(14, [2, 7]), 
(3, [3]), 
(9, [3, 3]), 
(15, [3, 5]), 
(5, [5]), 
(7, [7]), 
(11, [11]), 
(13, [13])] 

LƯU Ý: nó bao gồm n (= 16) là tốt, và tôi đã sử dụng danh sách thay vì bộ dữ liệu. Cả hai có thể dễ dàng được giải quyết nếu cần thiết, nhưng tôi sẽ để nó như một bài tập.

Answer 2

Đệ quy (pseudo-code):

def get_factorizations_of_all_numbers(start = starting_point 
            , end = end_point 
            , minp = mimimum_prime 
            ): 
    if start > end: 
     return Empty_List 
    if minp^2 > end: 
     return list_of_all_primes(start, end) 
    else 
     a = minp * get_factorizations_of_all_numbers(rounddown(start/minp) 
                , roundup(end/minp) 
                ) 
     b = get_factorizations_of_all_numbers(start 
              , end 
              , next_prime(minp) 
              ) 
     return append(a , b) 

get_factorizations_of_all_numbers(1, n, 2) 

Answer 3

Đây là một thực hiện rây-based (xin vui lòng tha mã un-pythonic :)):

def sieve(n): 
    # start each number off with an empty list of factors 
    # note that nums[n] will give the factors of n 
    nums = [[] for x in range(n)] 
    # start the counter at the first prime 
    prime = 2 
    while prime < n: 
     power = prime 
     while power < n: 
      multiple = power 
      while multiple < n: 
       nums[multiple].append(prime) 
       multiple += power 
      power *= prime 
     # find the next prime 
     # the next number with no factors 
     k = prime + 1 
     if k >= n: # no primes left!!! 
      return nums 
     # the prime will have an empty list of factors 
     while len(nums[k]) > 0: 
      k += 1 
      if k >= n: # no primes left!!! 
       return nums 
     prime = k 
    return nums 


def runTests(): 
    primes = sieve(100) 
    if primes[3] == [3]: 
     print "passed" 
    else: 
     print "failed" 
    if primes[10] == [2,5]: 
     print "passed" 
    else: 
     print "failed" 
    if primes[32] == [2,2,2,2,2]: 
     print "passed" 
    else: 
     print "failed" 

Các xét nghiệm:

>>> runTests() 
passed 
passed 
passed 

Trên máy của tôi, việc này mất 56 giây để chạy:

primes = sieve(14000000) # 14 million! 

Ví dụ:

>>> primes[:10] 
[[], [], [2], [3], [2, 2], [5], [2, 3], [7], [2, 2, 2], [3, 3]] 

>>> primes[10000] 
[2, 2, 2, 2, 5, 5, 5, 5] 

>>> primes[65536] 
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] 

>>> primes[6561] 
[3, 3, 3, 3, 3, 3, 3, 3] 

>>> primes[233223] 
[3, 17, 17, 269] 

Memory tiêu thụ: khoảng 50 triệu số nguyên, trong 14 triệu danh sách:

>>> sum(map(len, primes)) 
53303934