Project Euler

Wiki »

Problem 41 » 履歴 » リビジョン 2

リビジョン 1 (Noppi, 2024/01/15 08:30) → リビジョン 2/3 (Noppi, 2024/01/15 11:37)

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]] 
 # [[Problem 41]] 

 ## Pandigital Prime 
 We shall say that an $n$-digit number is pandigital if it makes use of all the digits $1$ to $n$ exactly once. For example, $2143$ is a $4$-digit pandigital and is also prime. 

 What is the largest $n$-digit pandigital prime that exists? 

 ## パンデジタル素数 
 n桁パンデジタルであるとは, 1からnまでの数を各桁に1つずつ持つこととする. 

 #下のリンク先にあるような数学的定義とは異なる 

 例えば2143は4桁[パンデジタル数](https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%B3%E3%83%87%E3%82%B8%E3%82%BF%E3%83%AB%E6%95%B0)であり, かつ素数である. n桁（この問題の定義では9桁以下）パンデジタルな素数の中で最大の数を答えよ. 

 ```scheme 
 (import (scheme base) 
         (gauche base) 
         (util combinations) 
         (math prime)) prime) 
         (scheme list)) 

 (define temp-primes (primes)) 

 (define (prime? num) 
   (= (car 
        (drop-while (cut < <> num) 
                    temp-primes)) 
      num)) 

 ; 考えられる組み合わせとしては 
 ; (1 2 3 4) 
 ; (1 2 3 4 5 6 7) 
 ; のみ 
 ; （他は全て 3 で割り切れる数となる） 
 (define possible-list 
   (map (^[lis] 
          (fold (^[n acc] 
                  (+ (* acc 10) 
                     n)) 
                0 
                lis)) 
        (append (permutations (iota 4 1)) 
                (permutations (iota 7 1))))) 

 (define prime-pandigital-list 
   (filter miller-rabin-prime? prime? 
           possible-list)) 

 (define answer-41 
   (apply max prime-pandigital-list)) 

 (format #t "41: ~d~%" answer-41) 
 ```