javascript实现Emrips反质数枚举的示例代码

今天看到一个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反质数枚举的示例代码就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • javascript实现Emrips反质数枚举的示例代码

    今天看到一个kata,提出一个"emirps"的概念:一个质数倒转后得到的是一个不同的质数,这个数叫做"emirps". 例如:13,17是质数,31,71也是质数,13和17是"emirps". 但是质数757,787,797是回文质数,这意味着反转的数字与原始数字相同,所以它们不被认为是"emirps". 题目要求写一个函数输入一个正整数n,返回小于n的"emirps"的个数,其中最大"emi

  • JavaScript使用Ajax上传文件的示例代码

    本文介绍了JavaScript使用Ajax上传文件的示例代码,分享给大家,具体如下: 实现文件的上传主要有两种方式: 使用form表单提交上传 html代码如下: <form id="uploadForm" enctype="multipart/form-data"> <input id="file" type="file" name="file"/> <button id=&

  • JavaScript/TypeScript 实现并发请求控制的示例代码

    场景 假设有 10 个请求,但是最大的并发数目是 5 个,并且要求拿到请求结果,这样就是一个简单的并发请求控制 模拟 利用 setTimeout 实行简单模仿一个请求 let startTime = Date.now(); const timeout = (timeout: number, ret: number) => { return (idx?: any) => new Promise((resolve) => { setTimeout(() => { const compa

  • Go语言实现枚举的示例代码

    在编程领域里,枚举用来表示只包含有限数量的固定值的类型,在开发中一般用于标识错误码或者状态机.拿一个实体对象的状态机来说,它通常与这个对象在数据库里对应记录的标识状态的字段值相对应. 在刚开始学编程的时候,你一定写过,至少见过直接使用魔术数字进行判断的代码.啥叫魔术数字呢,举个例子,要置顶一个文章的时候先判断文章是不是已发布状态. if (article.state == 2) {    // state 2 代表文章已发布 } 假如我们的代码里没有注释,或者等我们项目的代码里充斥着这些魔术数字

  • JavaScript用document.write()输出换行的示例代码

    当我们想用document.write()输出换行时,可能会第一时间想到加"\n",但是其实不能达到我们的想要效果,只会得到一个空格的效果. 正确的方法是使用:</br> 样例代码: <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <script> // 使用 \n 换行 ---> 错误的方法 document.write(&quo

  • JavaScript双向链表实现LRU缓存算法的示例代码

    目录 目标 什么是LRU 简介 硬件支持 寄存器 栈 代码实现 思路 链表节点数据结构 链表数据结构 LRUCache数据结构 完整代码 测试 目标 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构. 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 . void put(int key

  • JavaScript实现无缝轮播图的示例代码

    目录 上效果 一.实现过程 1)首先实现基本布局 2)主要样式 二.如何实现无缝呢 (重点来了) 思路: 主要代码 完整代码 花费一个下午从0到1实现的轮播图,当然还有很多需要改进的地方(欢迎提出需要改进的地方),等我再努力努力,将其封装成一个组件. 上效果 一.实现过程 1)首先实现基本布局 <div class="carousel-container"> //图片列表 <div class="carousel-list"></div

  • JavaScript实现扯网动画效果的示例代码

    目录 演示 技术栈 源码 css控制 js部分 演示 技术栈 JavaScript prototype(原型对象): 所有的 JavaScript 对象都会从一个 prototype(原型对象)中继承属性和方法.Date 对象从 Date.prototype 继承. Array 对象从 Array.prototype 继承. Person 对象从 Person.prototype 继承. 所有 JavaScript 中的对象都是位于原型链顶端的 Object 的实例. JavaScript 对象

  • JavaScript实现邮箱后缀提示功能的示例代码

    先来个基础的 需求 根据下面需求实现如示意图所示的邮箱输入提示功能,注意,根据要求只需实现下面功能 当用户没有任何输入时,提示框消失 当用户输入字符后,显示提示框,并且把用户输入的内容自动拼上邮箱后缀进行显示 暂时不用考虑示意图中的红色和蓝色背景色的逻辑 注意用户输入中前后空格需要去除 小优化编码 需求 如果我们输入的是 abc@1,这个时候出现的提示框内容是 abc@1@163.com abc@1@gmail.com abc@1@126.com -- 很明显,上面的提示框不是一个符合用户需求的

  • JavaScript中如何在一个循环中等待示例代码详解

    下面是如何使用for..of 循环来迭代一个数组并在循环内等待: const fun = (prop) => { return new Promise(resolve => { setTimeout(() => resolve(`done ${prop}`), 1000); }) } const go = async () => { const list = [1, 2, 3] for (const prop of list) { console.log(prop) console

随机推荐

其他