如何生成可以连接到新素数的素数对列表？

Question

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

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

为了实现这一点，我的想法是遍历列表，并将每个表示为列表的素数与表示为列表的所有其他素数连接起来。如果组合列表表示在通过 list->number 方法转换为数字后也是质数，我将其添加到最终列表，即 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, toby@telegraphics.com.au
(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.whosebug.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.whosebug.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)))))

; 
(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

不幸的是，有时它 returns 'pairs' 包含四个或更多值。例如，split-array-of-allowed-pairs 包含这样的对：

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

我们在这里看到更长的组合是 returned。我希望 ((3 6 7) (3)) 和 ((3) (3 6 7)) 分别表示为一对。他们最终以某种方式结合在一起。

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

提前致谢。

请在此处查看代码的要点，下面的两个测试都应该 return 为真：https://gist.github.com/erooijak/2d462ad429e6e05ddd25.

Answer 1

您的函数 get-prime-pairs 有几个问题。这是一个有效的非尾递归版本：

(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-all-prime-pairs.

尝试将列表lst的所有元素与列表的所有元素组合起来

辅助函数find-all-prime-pairs尝试将它的第一个参数（prime）与列表第二个参数（lst）的所有元素结合起来，并且returns所有组合是质数的对。在这种情况下，递归针对第二个参数 lst：如果它为空，则找不到对，否则它会将 prime 附加到 lst 的 car看看这是不是素数。如果为真那么函数returns得到的列表第一对和递归调用的结果对剩下的lst，否则它returns只是递归调用的结果.

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

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

换句话说，我建议你先把函数写成"normal"递归函数，然后，当你确定它可以工作时，如果需要的话，把它重写成尾递归（或迭代）（在上面的例子中，这留作练习）。

最后一点，考虑到 3367 不是素数，它等于 7 * 13 * 37。

Answer 2

public class PrimeConcatenation {
    public static void main(String[] args) {
        Scanner s1=new  Scanner(System.in);
        int num =s1.nextInt();
        int[] arr=new int[num];
        int[] res;
        int index=0;
        int count=0;
        for (int i = 2; i <=num; i++) {            
            if(prime(i))
            {
                arr[index]=i;
                index++;
//              System.out.println(""+i+""+prime(i));  
            }            
        }
        res=new int[index*index];
        int res_index=0;        
        for(int i=0;i<index;i++)
        {
            for(int j=0;j<index;j++)
            {
                String str=""+arr[i]+arr[j];
                if(prime(Integer.parseInt(str)))
                {
//                    System.out.println("val is "+str);
                    res[res_index]=Integer.parseInt(str);
                    res_index++;
                    count++;
                }                
            }
        }
        System.out.println(""+count);        
    }
    static boolean prime(int num)
    {
        boolean res;
        for(int i=2;i<num;i++)
        {
            if(num%i==0)
            {
                res=false;
                return res;
            }            
        }
        return true;
    }   
}

如何生成可以连接到新素数的素数对列表？

How to generate list of prime pairs that can be concatenated to new prime?

scheme