可逆素数

• 2019 年 11 月 3 日
• 筆記

可逆素数

问题描述

编写程序找出1-900之间所有的可逆素数(可逆素数是指一个素数的各位数值顺序颠倒后得到的数仍未素数,如113,311)

算法思路

1. 用筛法找到900以内素数表prime[]
2. 迭代prime[]所有的数,检测其相反数是否也为素数

代码示例

Python

  # 找出100-900的可逆素数    # 1. 构建素数表prime[],存放1-900的素数  # 2. 遍历prime[],找出可逆素数    pt = [True] * 1000 # 筛表  def isPrime(n):      if pt[n] :          for x in range(n,1000,n):              pt[x]=False          return True      else:          return False      # 1. 构建素数表  prime = [] # 素数表  for x in range(2,901):      if isPrime(x):          prime.append(x)    # 2. 遍历prime,找出可逆素数  for x in prime:      xx = str(x)      xx = int(xx[::-1]) # 字符串倒置      if isPrime(xx):          print(x)    

Java

import java.util.ArrayList;  import java.util.List;    public class 可逆素数 {        //1. 构建素数表prime[],存储1-900的素数      //2. 遍历prime,找出可逆素数      static boolean[] pt; // 筛表        static void init(){          pt = new boolean[1000];          for(int i=0;i<pt.length;i++){              pt[i]=true;          }      }        static boolean isPrime(int n){          if(pt[n]){              // 更新筛表              for(int i=n;i<pt.length;i+=n){                  pt[i]=false;              }              return true;          }else{              return false;          }      }        public static void main(String[] args) {          init();            List<Integer> prime = new ArrayList<>();          for(int i=2;i<901;i++){              if(isPrime(i)){                  prime.add(i);              }          }            for (Integer x : prime) {              StringBuilder sb = new StringBuilder(x+"");              sb = sb.reverse();              int y = new Integer(sb.toString());              if(isPrime(y)){                  System.out.println(x);              }          }      }    }