如何find0 – 100之间的素数?

在Javascript中,我将如何find0 – 100之间的素数? 我已经想过了,我不知道如何find它们。 我想过做x%x,但是我发现了这个明显的问题。 这是我迄今为止:但不幸的是,这是有史以来最糟糕的代码。

var prime = function (){ var num; for (num = 0; num < 101; num++){ if (num % 2 === 0){ break; } else if (num % 3 === 0){ break; } else if (num % 4=== 0){ break; } else if (num % 5 === 0){ break; } else if (num % 6 === 0){ break; } else if (num % 7 === 0){ break; } else if (num % 8 === 0){ break; } else if (num % 9 === 0){ break; } else if (num % 10 === 0){ break; } else if (num % 11 === 0){ break; } else if (num % 12 === 0){ break; } else { return num; } } }; console.log(prime()); 

以下是JavaScript中筛选实现的示例:

 function getPrimes(max) { var sieve = [], i, j, primes = []; for (i = 2; i <= max; ++i) { if (!sieve[i]) { // i has not been marked -- it is prime primes.push(i); for (j = i << 1; j <= max; j += i) { sieve[j] = true; } } } return primes; } 

然后getPrimes(100)将返回2到100(含)之间的所有素数的数组。 当然,由于内存限制,你不能在大的参数中使用它。

Java实现看起来非常相似。

这是我如何解决它。 将它从Java重写为JavaScript,所以如果有语法错误,请原谅。

 function isPrime (n) { if (n < 2) return false; /** * An integer is prime if it is not divisible by any prime less than or equal to its square root **/ var q = Math.floor(Math.sqrt(n)); for (var i = 2; i <= q; i++) { if (n % i == 0) { return false; } } return true; } 

如果一个数n不能被除了1和它自己之外的其他数字整除,那么这个数是n 。 另外,检查数字[2,sqrt(n)]就足够了。

这里是这个脚本的现场演示: http : //jsfiddle.net/K2QJp/

首先,创build一个函数来testing一个数是否为素数。 如果你想扩展Number对象,但是我决定只保持代码尽可能简单。

 function isPrime(num) { if(num < 2) return false; for (var i = 2; i < num; i++) { if(num%i==0) return false; } return true; } 

该脚本遍历数字小于2和1之间的每个数字,并testing是否存在没有余数的任何数字,如果将数字除以增量。 如果没有余数,这不是素数。 如果数字less于2,则不是素数。 否则,这是首要的。

然后做一个for循环遍历数字0到100,并用该函数testing每个数字。 如果是素数,则将该数字输出到日志。

 for(var i = 0; i < 100; i++){ if(isPrime(i)) console.log(i); } 

无论什么语言,在一个范围内寻找素数的最好和最容易find的方法之一是使用筛子 。

不会给你的代码,但这是一个很好的起点。

对于一个小范围,比如你的,最有效率的是预先计算数字。

我稍微修改了Sundaramalgorithm的Sieve,以减less不必要的迭代次数,它似乎非常快。

这个algorithm实际上比这个主题下最常用的@Ted Hopp解决scheme快两倍 。 解决在0 – 1M之间的78498素数在Chrome 55中需要20〜25毫秒,在FF 50.1中需要<90毫秒。 另外@ vitaly-t的下一个主要algorithm看起来很有趣,但结果也慢得多。

这是核心algorithm。 人们可以应用分割和线程来获得出色的结果。

 "use strict"; function primeSieve(n){ var a = Array(n = n/2), t = (Math.sqrt(4+8*n)-2)/4, u = 0, r = []; for(var i = 1; i <= t; i++){ u = (ni)/(1+2*i); for(var j = i; j <= u; j++) a[i + j + 2*i*j] = true; } for(var i = 0; i<= n; i++) !a[i] && r.push(i*2+1); return r; } var primes = []; console.time("primes"); primes = primeSieve(1000000); console.timeEnd("primes"); console.log(primes.length); 

如果一个数字不能被其他比所讨论数量低的素数整除,那么这个数字就是一个数字。

所以这build立了一个primes数组。 testing每个新的奇数候选人n除以现有的primes低于n 。 作为一个优化,它不考虑偶数,并且预先将2作为最后一步。

 var primes = []; for(var n=3;n<=100;n+=2) { if(primes.every(function(prime){return n%prime!=0})) { primes.push(n); } } primes.unshift(2); 

find0到n之间的素数。 你只需要检查数字x是否可以被0 – (x的平方根)之间的任何数字整除。 如果我们通过n并find0和n之间的所有素数,逻辑可以被实现为 –

  function findPrimeNums(n) { var x= 3,j,i=2, primeArr=[2],isPrime; for (;x<=n;x+=2){ j = (int) Math.sqrt (x); isPrime = true; for (i = 2; i <= j; i++) { if (x % i == 0){ isPrime = false; break; } } if(isPrime){ primeArr.push(x); } } return primeArr; } 

Luchian的答案为您提供了寻找素数的标准技术的链接。

效率较低但更简单的方法是将现有代码转换为嵌套循环。 注意到你除以2,3,4,5,6等等,然后把它变成一个循环。

鉴于这是作业,并且考虑到作业的目的是帮助你学习基本的编程,一个简单,正确,但效率低下的解决scheme应该是好的。

这是根据以前的素数值计算JavaScript中素数的最快方法。

 function nextPrime(value) { if (value > 2) { var i, q; do { i = 3; value += 2; q = Math.floor(Math.sqrt(value)); while (i <= q && value % i) { i += 2; } } while (i <= q); return value; } return value === 2 ? 3 : 2; } 

testing

 var value = 0, result = []; for (var i = 0; i < 10; i++) { value = nextPrime(value); result.push(value); } console.log("Primes:", result); 

产量

 Primes: [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ] 

这比在这里公布的其他替代方法更快,因为:

  • 它将循环限制与一个整数相alignment,
  • 它使用更短的迭代循环,跳过偶数。

它可以在大约130ms内给你第一个100,000个素数,或者在大约4秒内给你前100万个素数。

  function nextPrime(value) { if (value > 2) { var i, q; do { i = 3; value += 2; q = Math.floor(Math.sqrt(value)); while (i <= q && value % i) { i += 2; } } while (i <= q); return value; } return value === 2 ? 3 : 2; } var value, result = []; for (var i = 0; i < 10; i++) { value = nextPrime(value); result.push(value); } display("Primes: " + result.join(', ')); function display(msg) { document.body.insertAdjacentHTML( "beforeend", "<p>" + msg + "</p>" ); } 
 var isPrime = n => n>1&&Array.from({length:Math.floor(Math.sqrt(n))-1},(_,i)=>i+2).every(m=>n%m); // or var isPrime = n => n>1&&!/^(oo+)\1+$/.test('o'.repeat(n)) // inefficient for big numbers Array.from({length:101}, (_,i)=>i).filter(isPrime) 
 <code> <script language="javascript"> var n=prompt("Enter User Value") var x=1; if(n==0 || n==1) x=0; for(i=2;i<n;i++) { if(n%i==0) { x=0; break; } } if(x==1) { alert(n +" "+" is prime"); } else { alert(n +" "+" is not prime"); } </script> 

使用recursion结合平方根的规则,检查一个数是否为素数:

 function isPrime(num){ // An integer is prime if it is not divisible by any prime less than or equal to its square root var squareRoot = parseInt(Math.sqrt(num)); var primeCountUp = function(divisor){ if(divisor > squareRoot) { // got to a point where the divisor is greater than // the square root, therefore it is prime return true; } else if(num % divisor === 0) { // found a result that divides evenly, NOT prime return false; } else { // keep counting return primeCountUp(++divisor); } }; // start @ 2 because everything is divisible by 1 return primeCountUp(2); } 

Eratosthenes的筛子。 它的外观,但它简单,它的作品!

 function count_prime(arg) { arg = typeof arg !== 'undefined' ? arg : 20; //default value var list = [2] var list2 = [0,1] var real_prime = [] counter = 2 while (counter < arg ) { if (counter % 2 !== 0) { list.push(counter) } counter++ } for (i = 0; i < list.length - 1; i++) { var a = list[i] for (j = 0; j < list.length - 1; j++) { if (list[j] % a === 0 && list[j] !== a) { list[j] = false; // assign false to non-prime numbers } } if (list[i] !== false) { real_prime.push(list[i]); // save all prime numbers in new array } } } window.onload=count_prime(100); 

这是我的刺伤。

改变初始i=0从0到任何你想要的,第二个i<100从100到不同的范围内获得素数。

 for(var i=0; i<100; i++){ var devisableCount = 2; for(var x=0; x<=i/2; x++){ if(i !== 1 && i !== 0 && i !== x){ if(i%x === 0){ devisableCount++; } } } if(devisableCount === 3){ console.log(i); } } 

我试了10000000 – 这需要一些时间,但似乎是准确的。

如果我们已经尝试删除2,为什么要尝试删除4 (和6,8,10,12 )? 为什么试图删除9,如果已经尝试删除3 ? 如果11 * 11 = 121> 100,为什么要尝试删除11 ? 为什么试图删除任何奇数2 ? 为什么试图删除任何甚至以上2什么?

消除死亡testing,你会得到一个很好的代码testing100以下的素数。

而且你的代码还远远不是最糟糕的代码。 许多其他人会尝试将100除以99 。 但绝对冠军将产生2..96所有产品与2..96testing97是否在其中。 那真的是效率低得惊人。

当然,Eratosthenes的筛子要好得多,你可以有一个 – 对于100岁以下的人 – 没有布尔数组(也没有分割!)

 console.log(2) var m3=9, m5=25, m7=49, i=3 for( ; i<100; i+=2 ) { if( i!=m3 && i!=m5 && i!=m7) console.log(i) else { if( i==m3 ) m3+=6 if( i==m5 ) m5+=10 if( i==m7 ) m7+=14 } } "DONE" 

而这个着名的JS忍者代码

 var isPrime = n => Array(Math.ceil(Math.sqrt(n)+1)).fill().map((e,i)=>i).slice(2).every(m => n%m); console.log(Array(100).fill().map((e,i)=>i+1).slice(1).filter(isPrime)); 

使用ES6的新function构build的列表,特别是与发生器。 去加泰罗尼亚语的https://codepen.io/arius/pen/wqmzGp与我的学生上课。; 希望对你有帮助。

 function* Primer(max) { const infinite = !max && max !== 0; const re = /^.?$|^(..+?)\1+$/; let current = 1; while (infinite || max-- ) { if(!re.test('1'.repeat(current)) == true) yield current; current++ }; }; let [...list] = Primer(100); console.log(list); 

首先,将你的内部代码改为另一个循环( forwhile ),这样你可以为不同的值重复相同的代码。

对于你的问题更具体,如果你想知道一个给定的n是否为素数,则需要将它除以2和sqrt(n)之间的所有值。 如果任何模块是0,则不是素数。

如果你想find所有的素数,你可以加快速度,只检查n除以先前发现的素数。 加速这个过程的另一种方式是,除了2和3之外,所有素数都是6*k +或更less1。

如果你打算使用你将要在这个线程中呈现的gazillionalgorithm来学习记忆它们中的一些,

见面试问题:什么是recursion生成素数的最快方法?

使用以下function找出素数:

 function primeNumbers() { var p var n = document.primeForm.primeText.value var d var x var prime var displayAll = 2 + " " for (p = 3; p <= n; p = p + 2) { x = Math.sqrt(p) prime = 1 for (d = 3; prime && (d <= x); d = d + 2) if ((p % d) == 0) prime = 0 else prime = 1 if (prime == 1) { displayAll = displayAll + p + " " } } document.primeForm.primeArea.value = displayAll } 

检查数量是素数还是不使用JS函数

 function isPrime(num) { var flag = true; for(var i=2; i<=Math.ceil(num/2); i++) { if((num%i)==0) { flag = false; break; } } return flag; } 

这是testing号码是素数的一种方法。

 function isPrime(numb){ if (numb % 2 == 0) return false; for (var i=3; i<= Math.sqrt(numb); i = i + 2) { if (numb % i == 0) { return false; } } return true; } 

我修改了Rinto的答案,只是为了不想使用提示方法,只想看看程序打印素数。 它的工作

 for (n = 0; n < 100; n++) { var x = 1; if (n == 0 || n == 1) x = 0; for (i = 2; i < n; i++) { if (n % i == 0) { x = 0; break; } } if (x == 1) { // if prime print the numbers document.write(n); } else { // if not prime print the number do nothing } } 

这样的事情呢?

 next_prime: for (var i = 2; i < 100; i++){ for (var e = 2; e < i; e++){ if (i % e === 0) continue next_prime; } console.log(i + '<br>'); } 

这是我的解决scheme

 //find all prime numbers function showMePrimeNumbers(start, end){ var primes = []; for(var number = start; number < end; number++){ var primeNumberDividers = []; //there should only be 2: 1 & number for(var divider = 1; divider <= number; divider++){ if(number % divider === 0){ primeNumberDividers.push(divider); } } if(primeNumberDividers.length === 2){ primes.push(number); } } return primes; } console.log(showMePrimeNumbers(1, 100)); 

我已经创build了一个JSFiddle来展示它如何以可读的方式工作,

想法是有两个函数是Prim和getPrimeNumbers来分离function,以及使用Math.pow和2的初始值,因为它应该总是在那里,请参阅jsfiddle附加的jsFiddle

 window.onload = function() { (function() { var cont = document.getElementById('MainContainer'); var curEl = document.createElement('span'); var primeNumbers = [2]; function fillContent() { var primeNumbersContent = document.createTextNode(JSON.stringify(primeNumbers)); curEl.appendChild(primeNumbersContent); cont.appendChild(curEl); } function isPrime(n) { var divisor = 2; while (n > divisor) { if (Math.pow(divisor, 2) > n) { return true; } if (n % divisor == 0 || Math.sqrt(divisor) > n) { return false; } else { divisor++; } } return true; } function getPrimeNumbers(range) { for (var i = 3; i <= range; i+=2) { if (isPrime(i)) { primeNumbers.push(i); } } fillContent(primeNumbers); } getPrimeNumbers(11); })(); }; 

这里是我使用Eratosthenes筛法的解决scheme:

 function gimmePrimes(num) { numArray = []; // first generate array of numbers [2,3,...num] for (i = 2; i <= num; ++i) { numArray.push(i); } for (i = 0; i < numArray.length; ++i) { //this for loop helps to go through each element of array for (j = numArray[i]; j < numArray[numArray.length - 1]; ++j) { //get's the value of i'th element for (k = 2; j * k <= numArray[numArray.length - 1]; ++k) { //find the index of multiples of ith element in the array index = numArray.indexOf(j * k); if (index > -1) { //remove the multiples numArray.splice(index, 1); } } } } return numArray; //return result } gimmePrimes(100); 

这里是Brute-force iterative方法和Sieve of Eratosthenes方法的Sieve of Eratosthenes以find素数高达n。 在时间复杂度方面,第二种方法的性能优于第一种方法

蛮力迭代

 function findPrime(n) { var res = [2], isNotPrime; for (var i = 3; i < n; i++) { isNotPrime = res.some(checkDivisorExist); if ( !isNotPrime ) { res.push(i); } } function checkDivisorExist (j) { return i % j === 0; } return res; } 

Eratosthenes筛法

 function seiveOfErasthones (n) { var listOfNum =range(n), i = 2; // CHeck only until the square of the prime is less than number while (i*i < n && i < n) { listOfNum = filterMultiples(listOfNum, i); i++; } return listOfNum; function range (num) { var res = []; for (var i = 2; i <= num; i++) { res.push(i); } return res; } function filterMultiples (list, x) { return list.filter(function (item) { // Include numbers smaller than x as they are already prime return (item <= x) || (item > x && item % x !== 0); }); } } 

你可以使用这个素数的任何大小的数组。 希望这可以帮助

  function prime() { var num = 2; var body = document.getElementById("solution"); var len = arguments.length; var flag = true; for (j = 0; j < len; j++) { for (i = num; i < arguments[j]; i++) { if (arguments[j] % i == 0) { body.innerHTML += arguments[j] + " False <br />"; flag = false; break; } else { flag = true; } } if (flag) { body.innerHTML += arguments[j] + " True <br />"; } } } var data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; prime.apply(null, data); 
 <div id="solution"> </div> 
 public static void main(String[] args) { int m = 100; int a[] =new int[m]; for (int i=2; i<m; i++) for (int j=0; j<m; j+=i) a[j]++; for (int i=0; i<m; i++) if (a[i]==1) System.out.println(i); }