Emrips反质数枚举javascript实现

今天看到一个kata&＃xff0c;提出一个“emirps”的概念&＃xff1a;一个质数倒转后得到的是一个不同的质数&＃xff0c;这个数叫做“emirps”。

例如&＃xff1a;13,17是质数&＃xff0c;31,71也是质数&＃xff0c;13和17是“emirps”。 但是质数757,787,797是回文质数&＃xff0c;这意味着反转的数字与原始数字相同&＃xff0c;所以它们不被认为是“emirps”。

题目要求写一个函数输入一个正整数n&＃xff0c;返回小于n的“emirps”的个数&＃xff0c;其中最大“emirps”、以及所有小于n的“emirps”的和。

解题思路为先枚举出所有小于n的质数&＃xff0c;然后剔除回文质数以及颠倒后为合数的数。

先写判断质数的函数

主要根据三个数学结论&＃xff1a;

• 所有合数都是若干个质数的乘积
• 如一个数可以进行因式分解&＃xff0c;那么两个因数一定是一个小于等于sqrt(n)&＃xff0c;一个大于等于sqrt(n)。
• 所有大于3的质数都是6X&＃43;1或者6X-1这种形式&＃xff0c;也就是6的倍数的相邻的数&＃xff0c;但并不是所有6X&＃43;1或者6X-1都是质数。

第一个结论用反证法即可证明

第三个结论证明&＃xff1a;

我们把数字都表示为以下形式 6X-1、6X、6X&＃43;1、6X&＃43;2、6X&＃43;3、6X&＃43;4 (X为正整数)

6X &＃61;> 2*3x

6X&＃43;2 &＃61;> 2(3x&＃43;1)

6X&＃43;3 &＃61;> 3(2x&＃43;1)

6X&＃43;4 &＃61;> 2(3x&＃43;2) 可证明这些肯定不为质数&＃xff0c;即质数只能为6X-1或者6X-1

代码&＃xff1a;

再剔除回文质数以及颠倒后为合数的数

代码&＃xff1a;

最后输出想要的结果

代码&＃xff1a;

看一下输出结果和用时

n&＃61;1000000&＃xff1a;

&＃xfffc;

n&＃61;10000000&＃xff1a;

&＃xfffc;