素数回文以及素数相关总结

  • 普通筛素数法
  • 埃式筛法
  • 优化筛法
  • 整数分解(唯一分解定理)
  • 约数枚举
  • Hdu - 1431. 素数回文

普通筛素数法

这个也是普通的素数判定的方法，这个方法判定素数时间复杂度为O (sqrt(n))。

在这里插入图片描述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 static ArrayList<Integer> sieve(boolean[] is_prime, int MAX) { ArrayList<Integer> prime = new ArrayList<>(); is_prime[0] = is_prime[1] = false; // 01 不是素数 boolean flag; for (int i = 2; i <= MAX; i++) { flag = true; for (int j = 2; j * j <= i; j++) {// 根号i的时间复杂度 if (i % j == 0) { is_prime[i] = false; flag = false; break; } } if (flag) { prime.add(i); is_prime[i] = true; } } return prime; }

埃式筛法

在这里插入图片描述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 //经典的埃式筛法 static ArrayList<Integer> sieve(boolean[] is_prime, int MAX) { ArrayList<Integer> prime = new ArrayList<>(); Arrays.fill(is_prime, true); is_prime[0] = is_prime[0] = false; for (int i = 2; i <= MAX; i++) { if (is_prime[i]) { prime.add(i); for (int j = 2 * i; j <= MAX; j += i) is_prime[j] = false; } } return prime; }

优化筛法

  • 上面的方法还是有一些重复的计算，比如说在搞定素数2的时候，筛选掉6 (2 + 2 + 2)；而在搞定素数3的时候，也要筛选掉6 (3 + 3) ，所以此时重复筛选；

  • 解决办法是 只筛选小于等于i的素数和i的乘积，这样可以尽量的的减少重复的筛选，也不会遗漏；

    在这里插入图片描述
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 //优化筛法 static ArrayList<Integer> sieve2(boolean[] is_prime, int MAX) { ArrayList<Integer> prime = new ArrayList<>(); Arrays.fill(is_prime, true); is_prime[0] = is_prime[0] = false; for (int i = 2; i <= MAX; i++) { if (is_prime[i]) prime.add(i); for (int j = 0; j < prime.size() && prime.get(j) <= MAX / i; j++) {// MAX/i防止溢出 is_prime[prime.get(j) * i] = false; //筛掉 (小于等于i的素数 * i) 构成的合数 if (i % prime.get(j) == 0) //如果 i是 < i的素数的倍数 就不用筛了 break; } } return prime; }

整数分解(唯一分解定理)

题目链接

https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/1634.html

题目

在这里插入图片描述

解析

在这里插入图片描述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 import java.io.BufferedInputStream; import java.util.*; public class Main { static ArrayList<Integer> sieve(int MAX) { ArrayList<Integer> prime = new ArrayList<>(); boolean[] is_prime = new boolean[MAX + 1]; Arrays.fill(is_prime, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= MAX; i++) { if (is_prime[i]) { prime.add(i); for (int j = 2 * i; j <= MAX; j += i) { is_prime[j] = false; } } } return prime; } public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream(System.in)); int T = cin.nextInt(); while (T-- > 0) { int n = cin.nextInt(); ArrayList<Integer> prime = sieve(n); boolean isFirst = true; for (int i = 0; i < prime.size(); i++) { int num = prime.get(i); while (n % num == 0) { if (isFirst) { System.out.print(num); isFirst = false; } else System.out.print("*" + num); n /= num; } } System.out.println(); } } }

约数枚举

就是得到某个数的约数，和普通筛法有点像:

在这里插入图片描述

这里把上面的整数分解的保存也贴在这个代码里面:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 import java.util.ArrayList; import java.util.HashMap; public class TestPrime { //约数枚举 static ArrayList<Integer> divisor(int n){ ArrayList<Integer> res = new ArrayList<>(); for (int i = 1; i * i <= n; i++){ if(n % i == 0) res.add(i); if(i != n/i) res.add(n/i); } return res; } //整数分解 static HashMap<Integer,Integer> prime_factor(int n){ HashMap<Integer,Integer> map = new HashMap<>(); for(int i = 2; i * i <= n; i++){ while(n % i == 0){ if(map.containsKey(i)) { map.put(i, map.get(i) + 1); }else { map.put(i,1); } n /= i; } } if(n != 1) map.put(n,1); return map; } public static void main(String[] args){ System.out.println(divisor(12)); System.out.println("----测试分解素因子(唯一分解定理)-----"); HashMap<Integer,Integer>map = prime_factor(12); for(Integer num : map.keySet()){ System.out.println(num + " " + map.get(num)); } } }

运行结果:

在这里插入图片描述

Hdu - 1431. 素数回文

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1431

题目

在这里插入图片描述

解析

  • 先用素数筛法筛出0~9989899之间的素数，然后再遍历一遍，判断一下是不是回文，最后判断是不是在那个区间即可；

  • 注意这里使用的三种筛法，第一种会超时，第二种和第三种可以通过；
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 import java.io.BufferedInputStream; import java.util.*; /** * 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1431 */ public class Main { //提交时改成main // 经典筛法，超时 static ArrayList<Integer> primary(boolean[] is_prime,int MAX){ ArrayList<Integer> prime = new ArrayList<>(); is_prime[0] = is_prime[1] = false; // 01 不是素数 boolean flag; for(int i = 2; i <= MAX; i++){ //范围是1000 我筛选 0~2000内的素数 flag = true; for(int j = 2; j * j <= i; j++){// 根号i的时间复杂度 if(i % j == 0){ is_prime[i] = false; flag = false; break; } } if(flag){ prime.add(i); is_prime[i] = true; } } return prime; } //经典的埃式筛法 static ArrayList<Integer> sieve(boolean[] is_prime,int MAX){ ArrayList<Integer> prime = new ArrayList<>(); Arrays.fill(is_prime,true); is_prime[0] = is_prime[0] = false; for(int i = 2; i <= MAX; i++){ if(is_prime[i]){ prime.add(i); for(int j = 2 * i; j <= MAX; j+=i) is_prime[j] = false; } } return prime; } //优化筛法 static ArrayList<Integer> sieve2(boolean[] is_prime,int MAX){ ArrayList<Integer> prime = new ArrayList<>(); Arrays.fill(is_prime,true); is_prime[0] = is_prime[0] = false; for(int i = 2; i <= MAX; i++){ if(is_prime[i]) prime.add(i); for(int j = 0; j < prime.size() && prime.get(j) <= MAX / i; j++) { is_prime[prime.get(j) * i] = false; //筛掉 (小于等于i的素数 * i) 构成的合数 if(i % prime.get(j) == 0) //如果 i是 < i的素数的倍数 就不用筛了 break; } } return prime; } static boolean isPalindrome(int num){ int oldNum = num; int newNum = 0; //反过来计算 while(num > 0){ newNum = newNum * 10 + num % 10; num /= 10; } return newNum == oldNum; } static final int maxn = 9989899; //题目中最大的回文素数 public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream(System.in)); boolean[] is_prime = new boolean[maxn + 1]; // primary(is_prime,maxn); //超时 // sieve(is_prime,maxn); // ok sieve2(is_prime,maxn); // ok fast ArrayList<Integer> res = new ArrayList<>(); for(int i = 0; i <= maxn; i++ ){ if(is_prime[i] && isPalindrome(i)) res.add(i); } while(cin.hasNext()){ int a = cin.nextInt(); int b = cin.nextInt(); int num = 0; for(int i = 0; i < res.size(); i++){ num = res.get(i); if(num < a) continue; else if(num > b) break; // 直接退出 else System.out.println(num); } System.out.println(); } } }