今天看到一个kata,提出一个“emirps”的概念:一个质数倒转后得到的是一个不同的质数,这个数叫做“emirps”。
例如:13,17是质数,31,71也是质数,13和17是“emirps”。 但是质数757,787,797是回文质数,这意味着反转的数字与原始数字相同,所以它们不被认为是“emirps”。
题目要求写一个函数输入一个正整数n,返回小于n的“emirps”的个数,其中最大“emirps”、以及所有小于n的“emirps”的和。
解题思路为先枚举出所有小于n的质数,然后剔除回文质数以及颠倒后为合数的数。
先写判断质数的函数
主要根据三个数学结论:
所有合数都是若干个质数的乘积
如一个数可以进行因式分解,那么两个因数一定是一个小于等于sqrt(n),一个大于等于sqrt(n)。
所有大于3的质数都是6X+1或者6X-1这种形式,也就是6的倍数的相邻的数,但并不是所有6X+1或者6X-1都是质数。
第一个结论用反证法即可证明
第三个结论证明:
我们把数字都表示为以下形式 6X-1、6X、6X+1、6X+2、6X+3、6X+4 (X为正整数) 6X => 2*3x 6X+2 => 2(3x+1) 6X+3 => 3(2x+1) 6X+4 => 2(3x+2) 可证明这些肯定不为质数,即质数只能为6X-1或者6X-1
代码:
function isPrimeNumber(num){ if(num == 2 || num == 3){ return true; }/*2、3特殊处理*/ if(num % 6 != 1 && num % 6 != 5){ return false; }/*根据结论三排除*/ for(var i=5;i<=Math.sqrt(num);i+=6){ if(num % i == 0 || num % (i+2) == 0){ return false; } }/*根据结论二、结论三排除*/ return true; }
再剔除回文质数以及颠倒后为合数的数
代码:
function emirpNumber(num){ var reverseNumber = Number(String(num).split('').reverse().join('')) if(reverseNumber != num && isPrimeNumber(reverseNumber)){ return true; } else{ return false; } }
最后输出想要的结果
代码:
function findEmirp(n){ var emirpGroup = []; for(var i=1;i<n;i++){ if(isPrimeNumber(i) && emirpNumber(i)){ emirpGroup.push(i); } } return [ 'n为:' + n, '数量为:' + emirpGroup.length, '最大数:' + emirpGroup[emirpGroup.length - 1], '求和:' + emirpGroup.reduce(function(total,current){ return total + current; }) ] }
看一下输出结果和用时
n=1000000:
n=10000000:
以上这篇javascript实现Emrips反质数枚举的示例代码就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。
RTX 5090要首发 性能要翻倍!三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB,每个模块容量为2GB。其速度预设为32 Gbps(PAM3),但也可以降至28 Gbps,以提高产量和初始阶段的整体性能和成本效益。
据三星表示,GDDR7内存的能效将提高20%,同时工作电压仅为1.1V,低于标准的1.2V。通过采用更新的封装材料和优化的电路设计,使得在高速运行时的发热量降低,GDDR7的热阻比GDDR6降低了70%。
更新动态
- 雨林唱片《赏》新曲+精选集SACD版[ISO][2.3G]
- 罗大佑与OK男女合唱团.1995-再会吧!素兰【音乐工厂】【WAV+CUE】
- 草蜢.1993-宝贝对不起(国)【宝丽金】【WAV+CUE】
- 杨培安.2009-抒·情(EP)【擎天娱乐】【WAV+CUE】
- 周慧敏《EndlessDream》[WAV+CUE]
- 彭芳《纯色角3》2007[WAV+CUE]
- 江志丰2008-今生为你[豪记][WAV+CUE]
- 罗大佑1994《恋曲2000》音乐工厂[WAV+CUE][1G]
- 群星《一首歌一个故事》赵英俊某些作品重唱企划[FLAC分轨][1G]
- 群星《网易云英文歌曲播放量TOP100》[MP3][1G]
- 方大同.2024-梦想家TheDreamer【赋音乐】【FLAC分轨】
- 李慧珍.2007-爱死了【华谊兄弟】【WAV+CUE】
- 王大文.2019-国际太空站【环球】【FLAC分轨】
- 群星《2022超好听的十倍音质网络歌曲(163)》U盘音乐[WAV分轨][1.1G]
- 童丽《啼笑姻缘》头版限量编号24K金碟[低速原抓WAV+CUE][1.1G]