质数 JavaScript
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17389350/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Prime Numbers JavaScript
提问by HattrickNZ
Can someone please give me guidance on getting the primenumbers here? This is homework so I don't want the answer but some pointers would be greatly appreciated. It's really annoying me :(
有人可以指导我在这里获取质数吗？这是作业，所以我不想要答案，但将不胜感激。这真的让我很烦:(
I think I'm close. But this problems I have are number 25 and 35. These are not prime but this function is returning them
我想我很接近了。但是我遇到的这个问题是数字 25 和 35。这些不是质数但是这个函数正在返回它们
var getPrimeNumber = function(n) {
if(n === 1) return "";
else if(n == 2) return 2;
else if(n == 3) return 3;
else {
for(i=Math.floor(Math.sqrt(n)); i>=2; i--){
//console.log(i);//maybe another var in here?
if(n%i !==0 && n%2 !==0 && n%3 !== 0)
return n; // 25/Math.sqrt(25) will be equal to zero this is what gives me 25 !!!
}
}
};
回答by KooiInc
Based on this page, this would be a method for determining if a number is a prime number:
基于此页面，这将是一种确定数字是否为质数的方法：
function isPrime(number) {
let start = 2;
const limit = Math.sqrt(number);
while (start <= limit) {
if (number % start++ < 1) return false;
}
return number > 1;
}
In node.jsit takes about 250Ms for determining the prime numbers between 2 and 100.000.
在node.js这大约需要250毫秒确定2和100.000之间的素数。
回答by vitaly-t
Here's the fastest way to calculate primes in JavaScript, based on the previous prime value.
这是在 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;
}
Test
测试
var value, result = [];
for (var i = 0; i < 10; i++) {
value = nextPrime(value);
result.push(value);
}
console.log("Primes:", result);
Output
输出
Primes: [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]
It is very fast, because:
它非常快，因为：
- It aligns the loop limit to an integer;
- It uses a shorter iteration loop, skipping even numbers.
- 它将循环限制与整数对齐；
- 它使用较短的迭代循环，跳过偶数。
It can give you the first 100,000 primes in about 130ms, or the first 1m primes in about 4 seconds.
它可以在大约 130 毫秒内为您提供前 100,000 个素数，或在大约 4 秒内提供前 1m 个素数。
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>"
);
}回答by SaidbakR
There is a function that will return true if the number is prime and false if it is not:
有一个函数，如果数字是素数，则返回真，否则返回假：
function isPrime(x){
d = x-1;
while (d > 1){
if ((x % d) == 0) return false;
d--;
}
return true;
}
Checkout the demo: http://jsbin.com/velapabedi/1/
查看演示：http: //jsbin.com/velapabedi/1/
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JS Bin</title>
<script>
function isPrime(x){
d = x-1;
while (d > 1){
if ((x % d) == 0) return false;
d--;
}
return true;
}
if (isPrime(41)){
alert('Prime');
}
else{
alert('Not Prime');
}
</script>
</head>
<body>
</body>
</html>回答by Matt
Here's a simple "sieve" for prime numbers,which can be easily understood, and although it is a naive approach(as opposed to sophisticated efficient prime number tests such as the AKS test), it is pretty fast (10000 numbers tested in < 1 sec). It stores the found prime numbers in the array prim[]and tests by using the modulo function (%):
这是一个简单的素数“筛选”，很容易理解，虽然它是一种幼稚的方法（与复杂的高效素数测试如AKS 测试相反），但它非常快（在 < 1 中测试了 10000 个数字秒）。它将找到的素数存储在数组中prim[]并使用模函数 ( %) 进行测试：
The loop tests against already found prime numbers and exits if it is no prime number,i.e. if the modulo result is 0(regard the expression i % prim[j])===0). Otherwise, it adds it to the list of found prime numbers.
循环针对已经找到的素数进行测试，如果它不是素数，即如果模结果为 0（关于表达式i % prim[j])===0），则退出。否则，它将它添加到找到的素数列表中。
Notethat because the only even prime number is 2, the loop step is 2rather then 1, because from 3 onwards there can't be any further even prime numbers.
请注意，因为唯一的偶数是 2，所以循环步骤是 2而不是 1，因为从 3 开始就不能再有偶数了。
var MaxNum = 10000;
var prim;
function Main() {
MaxNum = GetMaxNum();
prim = CalculatePrimes(MaxNum);
CheckSome();
}
function CalculatePrimes(pMaxNum) {
Console.WriteLine("Calculating until " + pMaxNum + "...");
var _prim = [2];
if (pMaxNum > 2) {
for (var i = 3; i < pMaxNum; i += 2) {
var is_prim = true;
if (_prim.length > 0) {
for (var j = 0; j < _prim.length; j++) {
if ((i % _prim[j]) === 0) {
is_prim = false;
break;
}
}
}
if (is_prim) {
_prim.push(i);
}
}
}
Console.WriteLine("Prime numbers:");
for (var i = 0; i < _prim.length; i++) {
Console.Write(_prim[i] + " ");
}
Console.WriteLine();
Console.WriteLine("Found " + _prim.length + " prime numbers.");
Console.WriteLine();
return _prim;
}
// test some individual pre-calculated numbers
function CheckSome() {
var num1 = prim[prim.length - 1];
var num2 = num1 - 1;
Console.WriteLine("Test: " + num1.toString() + ". Is it a prime number? " + Is_prime(num1));
Console.WriteLine("Test: " + num2.toString() + ". Is it a prime number? " + Is_prime(num2));
}
function Is_prime(n) {
if (n > MaxNum) throw "ERROR: n must be <" + MaxNum + "!";
if (prim.indexOf(n) === -1)
return false;
else
return true;
};
// ------------ HELPERS to display on screen ------------
var Console = {
Section: 1,
SectionId: "#section1",
NewSection: function() {
var $currentSection = $(this.SectionId);
this.Section++;
this.SectionId = "#section" + this.Section.toString();
$currentSection.before('<div id="section' + this.Section.toString() + '"></div>');
},
Write: function(str) {
$(this.SectionId).append(str);
},
WriteLine: function(str) {
if (str !== undefined && str !== null && str !== "") this.Write(str);
this.Write("<br/>");
}
};
var GetMaxNum = function() {
var result = $("#MaxNumSelect option:selected").val();
return result;
}
$(document).ready(function() {
$("#MaxNumSelect").change(function() {
MaxNum = GetMaxNum();
Console.NewSection();
Main();
Console.WriteLine("---------------------------------");
});
Main();
});<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div>Select max number:
<select id="MaxNumSelect">
<option value="10000" default="default">10000</option>
<option value="100">100</option>
<option value="1000">1000</option>
<option value="100000">100000</option>
</select>
</div>
<div id="results">
<div id="section1"></div>
</div>In the above example, we have tested the first 10000 natural numbers. To decide if a given number is a prime number, you simply check if it is contained in the array prim:
在上面的例子中，我们测试了前 10000 个自然数。要确定给定数字是否为素数，只需检查它是否包含在数组中prim：
function Is_prime(n) {
if (n>MaxNum) throw "ERROR: n must be <"+CalcToNum+"!";
if (prim.indexOf(n)===-1)
return false;
else
return true;
};
Of course, in order for this to work the prime numbers need to be pre-calculated.
当然，为了使其工作，需要预先计算素数。
Example:alert(Is_prime(25));- returns false, because 25 is no prime number.
示例：alert(Is_prime(25));- 返回 false，因为 25 不是质数。
Note:The number range must be checked, because the function Is_primecan decide only for numbers which are previously tested by the sieve above. If the array is too small for the number to check (i.e. if not enough prime numbers are pre-calculated), an error is thrown.
注意：必须检查数字范围，因为该功能Is_prime只能决定先前由上面的筛子测试过的数字。如果数组太小而无法检查数字（即如果没有预先计算足够的素数），则会引发错误。
回答by lewdev
I considered the following in my implementation: Prime numbers are "natural numbers"and it is possible for negative values to be prime numbers. This is a more definitive solution with input sanitation:
我在我的实现中考虑了以下内容：质数是“自然数”，负值可能是质数。这是一个更明确的输入卫生解决方案：
function isPrime(num) {
//check if value is a natural numbers (integer)
//without this check, it returns true
if (isNaN(num) || num % 1 !== 0) {
return false;
}
num = Math.abs(num); //*negative values can be primes
if (num === 0 || num === 1) {
return false;
}
var maxFactorNum = Math.sqrt(num);
for (var i = 2; i <= maxFactorNum; i++) {
if (num % i === 0) {
return false;
}
}
return true;
}
//this method in action
for (var i = 1; i <= 40; i++) {
console.log(i + (isPrime(i) ? ", isPrime" : ""));
}
//checking anomalies
console.log(isPrime(1.22));
console.log(isPrime(1.44));
console.log(isPrime("string"));I hope my answer proves to be more readable code that also uses best practices. For example, some answers leave the square root calculation in the loop causing the method to run that calculation on every loop.
我希望我的回答被证明是更易读的代码，同时也使用了最佳实践。例如，某些答案将平方根计算留在循环中，导致该方法在每个循环中运行该计算。
回答by Microsmsm
This is my Answer
这是我的答案
var isPrime = function (n) {
if (n < 2) {
return false;
} else if (n === 2) {
return true;
}
for (var i = 2; i < n; i++) {
if (n%i === 0) {
return false;
} else if (i === n-1) {
return true;
}
}
}
console.log(isPrime(7));回答by Dan Zuzevich
function isPrime(number) {
// Immediate exit cases
switch(true){
case (number < 2):
return console.log("Please enter a number greater than or equal to 2.")
case (number === 2 || number === 3):
return console.log(number + " is a prime number!")
}
// Process number if it does not meet above requirements
var num = Math.floor(Math.sqrt(number))
for(var i = 2; i <= num; i++) {
if(number % i === 0)
return console.log(number + " is not a prime number")
else
return console.log(number + " is a prime number!")
}
}
isPrime(27) // 27 is a prime number!
isPrime(30) // 30 is not a prime number
isPrime(55) // 55 is a prime number!
isPrime(2) // 2 is a prime number!
回答by fatihk
You should return a boolvalue and new function can be:
您应该返回一个bool值，新函数可以是：
function(n) {
if(n === 1) { return false;}
else if(n == 2) { return true;}
else if(n == 3) { return true;}
else {
for(i=Math.floor(Math.sqrt(n));i>=2;i--){
//console.log(i);//maybe another var in here?
if(n%i ==0 || n%2 ==0 || n%3 == 0) {return false;}
}
}
return true;
};
In the OP, the control if(n%i !==0 && n%2 !==0 && n%3 !== 0) {return n;}was problematic because even if only single isatisfies this condition, the function returns the number as prime.
在 OP 中，控制if(n%i !==0 && n%2 !==0 && n%3 !== 0) {return n;}是有问题的，因为即使只有 singlei满足此条件，该函数也会将数字作为素数返回。
回答by Bjorn
In your if statement you got
在你的 if 语句中你得到
if(n%i !==0 && n%2 !==0 && n%3 !== 0)
you for loop is going till i >= 2, so the n%2 !== 0 is useless, when i = 2, your if would look like:
你的 for 循环一直持续到 i >= 2，所以 n%2 !== 0 没用，当 i = 2 时，你的 if 看起来像：
if(n%2 !==0 && n%2 !==0 && n%3 !== 0)
Thats 2x the same check, the same is for n%3, its already checked :).
那是 2 倍相同的检查，对于 n%3 也是如此，它已经检查过:)。
you should keep a bool to check the n%i !== 0, if it never reach this it's a prime.
你应该保留一个布尔值来检查 n%i !== 0，如果它永远不会达到这个，它就是一个质数。
Good luck with your homework :).
祝你的家庭作业好运:)。
回答by Khomeni
Do you want to know how to determine a number is prime or composite. This code make you understand easily. Input from a number 2.
你想知道如何确定一个数是质数还是合数。这段代码让你很容易理解。从数字 2 输入。
var p = prompt("Insert a number for check","");
var x = " is a prime number";
for(i=2; i<p; i++){
if(p%i === 0){
x = " is a composite number";
break;
}
}
alert(p+x);
