破解美眉微信号707829217

题目-破解美眉微信号 #

土生土长的北京妞儿，在胡同里长大，房不多，就一个四合院和近郊的别墅。不算美如天仙但还算标致，在清华读的经管，现在在做基金经理(不想被人肉，就不暴露单位啦)，个人擅长基本面分析，价值投资。现在只想找个聪明靠谱的IT男。硬性要求是年龄，不要超过88年，还有不要特别矮或胖。 我对智商的要求比较高，下面就出个题测试下。我的微信ID是大写字母NY后面跟着两个质数，大的在前，小的在后，乘积是707829217，可直接搜索添加，另外还有个附加题目，在刚刚微信ID的数字中，从1开始到这个数字的奇数序列里，一共出现了多少个3，如果私信我正确的答案，我将直接邀你见面!期待缘分降临~

美眉的微信号是NY后面跟两个质数，大的质数在前，小的在后。两个质数乘积是707829217，求美眉的微信号是多少？

数学知识 #

就是只能被1和自身整除，不能被其他数字整除。

简单推理：

    一个数n若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)（平方根），一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。

分析 #

上面这个数学知识，很重要，在判断是否是质数的时候，只要找 这个数字平方根 之前的数是否可以整除就好了。大大提升了效率。

Just Try #

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

参考答案 #

function isPrime(num){
  for(let i=2; i< Math.sqrt(num);i++){
    if(num%i == 0) return false;
  }
  return true;
}
function algorithm(n){
  for(let i=0; i< Math.sqrt(n);i++){
    if(isPrime(i) && (n%i==0) && isPrime(n/i)) return [i, n/i].join("")
  }
  return "";
}
function main(...param) {
  console.show("参数：" + param, "结果：" + algorithm(param))
  testPerformance(algorithm, param)
}
main(707829217);

结果是：8171 * 86627，微信号是：NY866278171

请你自动动手试一下：在线编程环境