如何生成可以连接到新素数的素数对列表? [英] How to generate list of prime pairs that can be concatenated to new prime?

问题描述

我有一个存储在变量 primes-list-split 中的素数列表，这些素数由 number->list 方法以列表格式表示.格式如下:2、3、5、7和11的质数列表为'((2) (3) (5) (7) (1 1)).

I have a list of primes stored in a variable primes-list-split that are represented in a list format by a number->list method. The format is as follows: the prime list of 2, 3, 5, 7, and 11 would be '((2) (3) (5) (7) (1 1)).

get-prime-pairs 将此列表作为输入，并尝试找到连接到另一个素数的每个组合.然后它应该在列表表示中的列表中返回这些对.因此，连接到也是素数的 3367 的对 3 367 应该在表示 ((3) (3 6 7)) 的列表中.

get-prime-pairs takes as input this list, and tries to find every combination that concatenates to another prime. Then it should return these pairs in a list in the list representation. So the pair 3 367 which concatenates to 3367 which is also prime should be in the list in the representation ((3) (3 6 7)).

为了实现这一点，我的想法是遍历列表，并将每个表示为列表的素数与表示为列表的所有其他素数连接起来.如果组合列表表示在通过 list->number 方法转换为数字后也是素数，我会将其添加到返回的最终列表中.

To achieve this my idea was to walk over the list and for every prime represented as a list concatenate it with all other primes represented as lists. If the combined list representation is also prime after a conversion to a number via the list->number method I add it to the final list which is returned.

代码实现如下:

(define (prime? n)
  (define (check-divisible n divisor)
    (cond ((= divisor 1) #t)
          ((= 0 (modulo n divisor)) #f)
          (else (check-divisible n (- divisor 1)))))
  (cond ((<= n 1) #f)
        ((= n 2) #t)
        ((even? n) #f)
        (else (check-divisible n (truncate (sqrt n))))))

; Copyright (C) 2011 Toby Thain, [e-mail]
(define (primes-up-to n)
  (let ((sieve (make-vector (+ n 1) #t)))
    (define (test-prime i)
      (define (is-prime? idx)
        (vector-ref sieve idx))
      (define (not-prime! idx)
        (vector-set! sieve idx #f))
      (define (remove-multiples i step)
        (when (<= i n)
          (not-prime! i)
          (remove-multiples (+ i step) step)))
      (if (> i n)
          '()
          (if (is-prime? i)
              (begin
                (remove-multiples i i)
                (cons i (test-prime (+ i 1))))
              (test-prime (+ i 1)))))
    (test-prime 2)))

(define primes-list (primes-up-to 100000))


;; From list generate split arrays of allowed pairs

; www.stackoverflow.com/questions/12834562/scheme-number-to-list#12841962
(define (number->list n)
  (let loop ((n n) (acc '()))
    (if (< n 10)
        (cons n acc)
        (loop (quotient n 10)
              (cons (remainder n 10) acc)))))

; www.stackoverflow.com/questions/1683479/how-to-convert-a-list-to-num-in-scheme#1688960
(define (list->number lst)
  (let loop ((n 0) (lst lst))
    (if (empty? lst)
        n
        (loop (+ (* 10 n) (car lst)) (cdr lst)))))

; http://stackoverflow.com/questions/31909685/how-can-i-filter-null-values-from-this-list
(define primes-list-split 
  (map number->list primes-list))

(define (get-prime-pairs lst)
  (define (split lst pos)
    (list (drop-right lst pos) (take-right lst pos)))
  (define (get-prime-pairs-iter n acc)
    (if (zero? n) 
        (if 
         (or (null? acc) 
             ; filter out those values that start with leading zero
             (zero? (caar acc)) 
             (zero? (caadr acc))) 
         '() 
         (list acc))
        (get-prime-pairs-iter 
         (- n 1) 
         (let ((s (split lst n)))
           (if (and (prime? (list->number (car s)))
                    (prime? (list->number (cadr s))))
               (append s acc)
               acc)))))
  (get-prime-pairs-iter (- (length lst) 1) '()))

(define split-array-of-allowed-pairs 
  (append-map get-prime-pairs primes-list-split))

split-array-of-allowed-pairs 

不幸的是，有时它会返回包含四个或更多值的对".例如，split-array-of-allowed-pairs 包含这样的对:

Unfortunately, sometimes it returns 'pairs' that contains of four or more values. For example, split-array-of-allowed-pairs contains pairs like this:

((...)
((3) (6 4 3))
((3) (6 5 9))
((3 6 7) (3) (3) (6 7 3))
((3 6 7) (7) (3) (6 7 7))
(...))

我们在这里看到返回了更长的组合.我希望 ((3 6 7) (3)) 和 ((3) (3 6 7)) 都分别表示为一对二.不知何故，它们最终结合在一起.

We see here that longer combinations are returned. I want ((3 6 7) (3)) and ((3) (3 6 7)) to be both represented separately as a pair of two. Somehow they end up combined.

我的方法有什么问题，有人知道我该如何解决吗?

What is wrong in my method and does anyone know how I can fix it?

提前致谢.

请参阅此处的代码要点，其中包含以下两个测试均应返回 true:https://gist.github.com/erooijak/2d462ad429e6e05ddd25.

See the gist here for the code with two tests below that should both return true: https://gist.github.com/erooijak/2d462ad429e6e05ddd25.

推荐答案

你的函数 get-prime-pairs 有几个问题.这是一个有效的非尾递归版本:

Your function get-prime-pairs has several problems. Here is a working, non-tail recursive version:

(define (get-prime-pairs lst)
  (define (find-all-prime-pairs prime lst)
    (if (null? lst)
        '()
        (if (prime? (list->number (append prime (car lst))))
            (cons (list prime (car lst))
                  (find-all-prime-pairs prime (cdr lst)))
            (find-all-prime-pairs prime (cdr lst)))))
  (append-map (lambda (x) (find-all-prime-pairs x lst)) lst))

(define split-array-of-allowed-pairs (get-prime-pairs primes-list-split))

这是它的工作原理.

函数 get-prime-pairs 通过调用函数 find 尝试将列表 lst 的所有元素与列表的所有元素组合起来-all-prime-pairs.

The function get-prime-pairs tries for all the element of list lst to combine them with all the elements of list, by calling the function find-all-prime-pairs.

辅助函数 find-all-prime-pairs 尝试将其第一个参数 (prime) 与列表第二个参数 (lst)，并返回组合为素数的所有对.在这种情况下，递归在第二个参数 lst 上:如果它为空，则找不到对，否则将 prime 附加到 car 的 lst 看看这是否是一个质数.如果为真，则函数返回由第一对获得的列表和对 lst 其余部分的递归调用的结果，否则它只返回递归调用的结果.

The auxiliary function find-all-prime-pairs tries to combine its first argument (prime) with all the elements of the list second argument (lst), and returns all the pairs where the combination is a prime number. In this case the recursion is on the second argument, lst: if it is empty, then no pair can be found, otherwise it appends prime to the car of lst to see if this is a prime number. If this is true then the function returns the list obtained by the first pair and the result of the recursive call to the rest of lst, otherwise it returns simply the result of the recursive call.

在我看来，您的递归不起作用的主要问题是，将递归函数编写为尾递归作为第一次尝试并不是使其正确的最佳方法.所以，我敢建议你考虑编程的基本规则:

It seems to me that the main problem for which your recursion does not work is that writing a recursive function as tail-recursive as first try is not the best way to get it correct. So, I dare to suggest you to consider the foundamental rule of programming:

首先，让你的程序工作，然后，如果有必要，让它高效.

First, make your program work, then, and if it necessary, make it efficient.

换句话说，我建议你先把这个函数写成一个普通"的递归函数，然后，当你确定它可以工作时，如果有必要的话，把它改写成尾递归(或迭代)(在上面如果这留作练习).

In other words, I suggest you first to write the function as a "normal" recursive function, and then, when you are sure that it works, rewrite it as tail recursive (or iterative) if necessary (and in the above case this is left as an exercise).

最后要注意的是，3367 不是质数，等于 7 * 13 * 37.

As final note, consider that 3367 is not a prime number, being equal to 7 * 13 * 37.

这篇关于如何生成可以连接到新素数的素数对列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！