欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

打印1~100之间的质数

程序员文章站 2024-03-14 19:41:35
...

学习如逆水行舟,不进则退,进入程序猿的行列听到的最多的就是这个行业发展很快要不断的进行学习,一个好的程序猿是在不断坚持学习的

今天就来说一下1~100之间的质数的计算方法:

1~100之间的质数:我们都知道质数的特点是除了1和它本身,没有其他的因数,这就给了我们一个筛选的条件,也可以作为其判断条件,下面先来说一种思路比较简单但是执行次数较多的方法:

flag的作用我在数组去重中有写过,代码中我也进行啦注释,如果对于此段代码中的flag的作用看不懂的亲们可以去翻看一下我写的数组去重的那篇博客(https://my.oschina.net/u/3521003/blog/1520617);

现在我们先来说一下思路:根据质数的特点除了1和它本身之外没有其他的因数,也就是说从2开始一直到它的前一个数都是不能被它除尽的,这里还要补充一点:1既不是质数也不是和数,所以我们在开始循环的时候就可以将其排除。

<script>
    var flag;   //定义一个flag用来判断是否进入了小循环中的判断语句
  for(i=2;i<100;i++){  //在上面我们已经说过,1既不是质数也不是和数,所以我们的循环可以从2开始
      flag=false;  //当每次进入大循环的时候,给flag赋一个初始值,这个初始值为false
      for(var j=2;j<i;j++){  //由于1可以被所有的数除尽,我们让除数的循环是从2开始的
          if(i%j==0){        //如果i取余j的值为0的话,则说明除了1和它自身之外还有其他的因数;则执行下面的代码
              flag=true;   //当判断为真,执行此语句,给flag赋值为true
              break;      //当if里面的代码被执行的时候,说明这个数字不是我们想要的,所以可以结束本次小循环
          }
      }
      if(!flag){       //当if判断条件为真的时候,才会执行下面的代码,也就是当flag为false的时候,数字才会被打印出来。
          document.write(i+"<br>");
      }
  }
</script>

上面这种方法没有太多绕的地方,属于简单易懂型的,但是由于循环次数太多,不利于提高性能,所以下面我们将会对其进行一定的优化。

现在我们来说一下思路:根据质数的特点除了1和它本身之外没有其他的因数,也就是说从2开始一直到它的前一个数都是不能被它除尽的,1-100之间的所有的非质数都是可以被2~7之间的数某一个数除尽的(现在我们讨论的范围是0~100之间的,如果超出100,则此方法就不适用啦),但是2,3,5,7这几个也是质数,如果进行小循环的判断de话则会被丢弃掉,所以就先把这四个数字给添加到新的数组中。

注意:下面代码中用到的push()方法为数组中中的方法,用于向数组中插入数据。

<script>
        var flag;  //定义一个flag用来判断是否进入了小循环中的判断语句
        var temp=[];  //定义一个新的空数组,来盛放找到的质数
        for(i=2;i<100;i++){  //在上面我们已经说过,1既不是质数也不是和数,所以我们的循环可以从2开始
            flag=false;      //当每次进入大循环的时候,给flag赋一个初始值,这个初始值为false
            if(i===2 || i===3 || i==5  ||i==7){  //先在大循环中进行判断,如果进入循环的数为2,3,5,7则直接添加到定义的数组中国
                temp.push(i);   //将i的值添加到新的数组中
            }
            for(var j=2;j<=7;j++){   //1-100之间的所有的非质数都是可以被2~7之间的数某一个数除尽的,将此作为一个判断条件
                if(i%j==0){     //如果i取余j的值为0的话,则说明除了1和它自身之外还有其他的因数;则执行下面的代码
                    flag=true;   //当判断为真,执行此语句,给flag赋值为true
                    break;          //当if里面的代码被执行的时候,说明这个数字不是我们想要的,所以可以结束本次小循环
                }
            }
            if(!flag){      /当if判断条件为真的时候,才会执行下面的代码,也就是当flag为false的时候,数字才会被添加到新的数组中。
                temp.push(i);
            }
        }
        console.log(temp);
</script>

上面的方法虽然循环执行的次数减少啦很多,但是对于大于100的数字就不适用啦,所以如果想要打印出从n~m之间的质数,还是建议适用第一种方法。下面我将第一种方法封装成一个函数。

function prime(n,m) {  //定义一个函数,并给他两个两个参数,第一个是起始数字,第二个是结束数字
    var flag;   //定义一个flag用来判断是否进入了小循环中的判断语句
    var temp=[];  //定义一个新的空数组,来盛放找到的质数
    for(i=n;i<=m;i++){  //从哪一个数开始进行判断,即将其赋给i为初始值,m为判断是否结束大循环的条件
        flag=false;   //当每次进入大循环的时候,给flag赋一个初始值,这个初始值为false
        if(i<=1){    //由于传入数值具有不确定性,所以先要将那些确定不为质数的数字先排除,负数不为质数,0、1不为质数
            flag=true;  //当此段代码被执行,说明不是我们想要的数字,将flag赋值为true
            continue;   //跳出本次循环,进入下次循环
        }
        for(var j=2;j<i;j++){  //由于1可以被所有的数除尽,我们让除数的循环是从2开始的
            if(i%j==0){     //如果i取余j的值为0的话,则说明除了1和它自身之外还有其他的因数;则执行下面的代码
                flag=true;  //当判断为真,执行此语句,给flag赋值为true
                break;      //当if里面的代码被执行的时候,说明这个数字不是我们想要的,所以可以结束本次小循环
            }
        }
        if(!flag){
            temp.push(i);//当if判断条件为真的时候,才会执行下面的代码,也就是当flag为false的时候,数字才会添加到新的数组中
        }
    }
    return temp;
}

 

下面再来补充一种方法,这回方法的性能更好,循环次数更少,但是下面这种方法更加的偏向数学一些。

<script>
    var flag;
    var count=0;
  for(i=2;i<100;i++){
      flag=false;
      for(var j=2;j<=Math.floor(Math.sqrt(i));j++){ //利用内置对象的开平方的方法
          if(i%j==0){
              flag=true;
              break;
          }
          count++;
      }
      if(!flag){
          document.write(i+"<br>");
      }

  }
  alert(count);
</script>

除了上面那种方法,下面还有一种方法,所以说一个需求的实现是多种方式的,但是我们要追求简洁还能提高性能的方法

<script>
    function pr(n){  //创建一个函数,对于是否是质数进行判断
        var a=true;
        for(var i=2;i<n;i++){
            if(n%i===0){
                a=false;
            }
        }
        return  a;
    }

    function area(m,n){  //这个函数实现啦可以找到从m到n之间的质数
        m<n;
        for(i=0;i<=n-m;i++){
             var a=m+i;
            if(pr(a)===true){
                console.log(a)
            }else{
                continue;
            }

        }
    }
        area(0,100);
</script>

 

转载于:https://my.oschina.net/u/3521003/blog/1522896