圆形素数 [英] Circular prime numbers

问题描述

我正在尝试将以下测试数字是否为质数的函数转换为测试整数是否为圆形质数的另一函数. 例如. 1193年是圆形素数，自1931年以来，9311和3119都是素数. 因此，我需要旋转整数并测试数字是否为质数.有任何想法吗? 注意:我是Haskell编程的新手

I am trying to convert the following function which test the number if it's prime to another one that test if the integer is a circular prime. eg. 1193 is a circular prime, since 1931, 9311 and 3119 all are also prime. So i need to rotate the digits of the integer and test if the number is prime or not. any ideas? note: I am new to Haskell Programming

isPrime ::  Integer -> Bool

isPrime 1 = False
isPrime 2 = True
isPrime n 
 | (length [x | x <- [2 .. n-1],  n  `mod` x == 0]) > 0 = False
 | otherwise = True 


isCircPrime ::  Integer -> Bool

推荐答案

您可以通过以下方式轻松实现isPrime函数的效率和高雅性:

You can improve the efficiency and elegance of your isPrime function easily by implementing it as:

isPrime ::  Integral i => i -> Bool
isPrime 1 = False
isPrime n = all ((/=) 0 . mod n) (takeWhile (\x -> x*x <= n) [2..])

为了旋转数字，我们可以在这里使用两个帮助函数:一个将数字转换为数字列表，另一个将数字列表转换为数字，我们相反地这样做，因为实施起来更方便，但没关系:

In order to rotate numbers, we can make use of two helper functions here: one to convert a number to a list of digits, and one to convert a list of digits to a number, we do this in reverse, since that is more convenient to implement, but will not matter:

num2dig :: Integral i => i -> [i]
num2dig n | n < 10 = [n]
          | otherwise = r : num2dig q
    where (q, r) = quotRem n 10


dig2num :: (Foldable t, Num a) => t a -> a
dig2num = foldr ((. (10 *)) . (+)) 0

现在，我们可以制作一个简单的函数来生成一系列项目的所有旋转:

Now we can make a simple function to generate, for a list of items, all rotations:

import Control.Applicative(liftA2)
import Data.List(inits, tails)

rots :: [a] -> [[a]]
rots = drop 1 . liftA2 (zipWith (++)) tails inits

所以我们可以用它来构造所有的旋转数字:

So we can use this to construct all rotated numbers:

rotnum :: Integral i => i -> [i]
rotnum = map dig2num . rots . num2dig

例如1425的轮换数字为:

Prelude Control.Applicative Data.List> rotnum 1425
[5142,2514,4251,1425]

我将对这些数字使用isPrime作为练习.

I leave using isPrime on these numbers as an exercise.

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