用JS写求素数

JavaScript010

用JS写求素数,第1张

    var a=n//n为输入所测的数值

    var b=1//这里不懂,下面关于b是做什么的都不明白

    if(a==0||a==1){

        document.write("0或1不是素数")

    }else{

        for(var i=2i<ai++){

            if(a%i==0){//没有余数,能整除

                b=0 //这就是一个标记,记录a有被某个数整除了

                break

            }

        }

        if(b){

            document.write(a+"是素数")

        }else{

            document.write(a+"不是素数")

        }

    }

以下代码可以实现JavaScript求n个素数,当n=500时满足题目需求。

function prime(n){

    var primeArr = [2]

    var isPrime = function(num, primeList){

        if(num == 2){

            return true

        }

        for(var i = 3, iLen = Math.sqrt(num), j = 1 i <= iLen i = primeList[j++]){

            if(num % i == 0){

                return false

            }

        }

        return true

    }

    if(isNaN(n) || n < 1){

        return []

    }

    for(var i = 3,  i < n i += 2){

        if(isPrime(i, primeArr)){

            primeArr.push(i)

        }

    }

    return primeArr

}

prime(100)

//函数调用

prime(100)//计算100以内的素数:

素数即除去1和其本身两个数之外,不能被任何数整除的整数。

由公理可知,如果一个整数能被分解成多个整数,则必有一个数不大于该整数的平方根(反证法可知,如果分解成的两个数都大于平方根,则乘积必大于原数),故在循环时,只需循环到该数的平方根即(Math.sqrt(num)为求平方根)

如果一个数能被2整除,则除2之外其他数都不是素数,故从3开始遍历能够减少循环次数

如果一个数能够被分解,则最终分解结果必然为多个素数之积,故循环时只需要尝试之前算好的素数能否整除当前的数,极大减少循环次数