可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效,请关闭广告屏蔽插件后再试):
问题:
In Javascript how would i find prime numbers between 0 - 100? i have thought about it, and i am not sure how to find them. i thought about doing x % x but i found the obvious problem with that.
this is what i have so far:
but unfortunately it is the worst code ever.
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());
回答1:
Here\'s an example of a sieve implementation in 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;
}
Then getPrimes(100)
will return an array of all primes between 2 and 100 (inclusive). Of course, due to memory constraints, you can\'t use this with large arguments.
A Java implementation would look very similar.
回答2:
Here\'s how I solved it. Rewrote it from Java to JavaScript, so excuse me if there\'s a syntax error.
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;
}
A number, n
, is a prime if it isn\'t divisible by any other number other than by 1 and itself. Also, it\'s sufficient to check the numbers [2, sqrt(n)].
回答3:
Here is the live demo of this script: http://jsfiddle.net/K2QJp/
First, make a function that will test if a single number is prime or not. If you want to extend the Number object you may, but I decided to just keep the code as simple as possible.
function isPrime(num) {
if(num < 2) return false;
for (var i = 2; i < num; i++) {
if(num%i==0)
return false;
}
return true;
}
This script goes through every number between 2 and 1 less than the number and tests if there is any number in which there is no remainder if you divide the number by the increment. If there is any without a remainder, it is not prime. If the number is less than 2, it is not prime. Otherwise, it is prime.
Then make a for loop to loop through the numbers 0 to 100 and test each number with that function. If it is prime, output the number to the log.
for(var i = 0; i < 100; i++){
if(isPrime(i)) console.log(i);
}
回答4:
Whatever the language, one of the best and most accessible ways of finding primes within a range is using a sieve.
Not going to give you code, but this is a good starting point.
For a small range, such as yours, the most efficient would be pre-computing the numbers.
回答5:
I have slightly modified the Sieve of Sundaram algorithm to cut the unnecessary iterations and it seems to be very fast.
This algorithm is actually two times faster than the most accepted @Ted Hopp\'s solution under this topic. Solving the 78498 primes between 0 - 1M takes like 20~25 msec in Chrome 55 and < 90 msec in FF 50.1. Also @vitaly-t\'s get next prime algorithm looks interesting but also results much slower.
This is the core algorithm. One could apply segmentation and threading to get superb results.
\"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 = (n-i)/(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);
The loop limits explained:
Just like the Sieve of Erasthotenes, the Sieve of Sundaram algorithm also crosses out some selected integers from the list. To select which integers to cross out the rule is i + j + 2ij ≤ n where i and j are two indices and n is the number of the total elements. Once we cross out every i + j + 2ij, the remaining numbers are doubled and oddified (2n+1) to reveal a list of prime numbers. The final stage is in fact the auto discounting of the even numbers. It\'s proof is beautifully explained here.
Sieve of Sundaram is only fast if the loop indices start and end limits are correctly selected such that there shall be no (or minimal) redundant (multiple) elimination of the non-primes. As we need i and j values to calculate the numbers to cross out, i + j + 2ij up to n let\'s see how we can approach.
i) So we have to find the the max value i and j can take when they are equal. Which is 2i + 2i^2 = n. We can easily solve the positive value for i by using the quadratic formula and that is the line with t = (Math.sqrt(4+8*n)-2)/4,
j) The inner loop index j should start from i and run up to the point it can go with the current i value. No more than that. Since we know that i + j + 2ij = n, this can easily be calculated as u = (n-i)/(1+2*i);
While this will not completely remove the redundant crossings it will \"greatly\" eliminate the redundancy. For instance for n = 50 (to check for primes up to 100) instead of doing 50 x 50 = 2500, we will do only 30 iterations in total. So clearly, this algorithm shouldn\'t be considered as an O(n^2) time complexity one.
i j v
1 1 4
1 2 7
1 3 10
1 4 13
1 5 16
1 6 19
1 7 22 <<
1 8 25
1 9 28
1 10 31 <<
1 11 34
1 12 37 <<
1 13 40 <<
1 14 43
1 15 46
1 16 49 <<
2 2 12
2 3 17
2 4 22 << dupe #1
2 5 27
2 6 32
2 7 37 << dupe #2
2 8 42
2 9 47
3 3 24
3 4 31 << dupe #3
3 5 38
3 6 45
4 4 40 << dupe #4
4 5 49 << dupe #5
among which there are only 5 duplicates. 22, 31, 37, 40, 49. The redundancy is around 20% for n = 100 however it increases to ~300% for n = 10M. Which means a further optimization of SoS bears the potentital to obtain the results even faster as n grows. So one idea might be segmentation and to keep n small all the time.
So OK.. I have decided to take this quest a little further.
After some careful examination of the repeated crossings I have come to the awareness of the fact that, by the exception of i === 1
case, if either one or both of the i
or j
index value is among 4,7,10,13,16,19... series, a duplicate crossing is generated. Then allowing the inner loop to turn only when i%3-1 !== 0
, a further cut down like 35-40% from the total number of the loops is achieved. So for instance for 1M integers the nested loop\'s total turn count dropped to like 1M from 1.4M. Wow..! We are talking almost O(n) here.
I have just made a test. In JS, just an empty loop counting up to 1B takes like 4000ms. In the below modified algorithm, finding the primes up to 100M takes the same amount of time.
I have also implemented the segmentation part of this algorithm to push to the workers. So that we will be able to use multiple threads too. But that code will follow a little later.
So let me introduce you the modified Sieve of Sundaram probably at it\'s best when not segmented. It shall compute the primes between 0-1M in about 15-20ms with Chrome V8 and Edge ChakraCore.
\"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 < (n-1)/3; i++) a[1+3*i] = true;
for(var i = 2; i <= t; i++){
u = (n-i)/(1+2*i);
if (i%3-1) 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);
Well... finally I guess i have implemented a sieve (which is originated from the ingenious Sieve of Sundaram) such that it\'s the fastest JavaScript sieve that i could have found over the internet, including the \"Odds only Sieve of Eratosthenes\" or the \"Sieve of Atkins\". Also this is ready for the web workers, multi-threading.
Think it this way. In this humble AMD PC for a single thread, it takes 3,300 ms for JS just to count up to 10^9 and the following optimized segmented SoS will get me the 50847534 primes up to 10^9 only in 14,000 ms. Which means 4.25 times the operation of just counting. I think it\'s impressive.
You can test it for yourself;
console.time(\"tare\");
for (var i = 0; i < 1000000000; i++);
console.timeEnd(\"tare\");
And here i introduce you to the segmented Seieve of Sundaram at it\'s best.
\"use strict\";
function findPrimes(n){
function primeSieve(g,o,r){
var t = (Math.sqrt(4+8*(g+o))-2)/4,
e = 0,
s = 0;
ar.fill(true);
if (o) {
for(var i = Math.ceil((o-1)/3); i < (g+o-1)/3; i++) ar[1+3*i-o] = false;
for(var i = 2; i < t; i++){
s = Math.ceil((o-i)/(1+2*i));
e = (g+o-i)/(1+2*i);
if (i%3-1) for(var j = s; j < e; j++) ar[i + j + 2*i*j-o] = false;
}
} else {
for(var i = 1; i < (g-1)/3; i++) ar[1+3*i] = false;
for(var i = 2; i < t; i++){
e = (g-i)/(1+2*i);
if (i%3-1) for(var j = i; j < e; j++) ar[i + j + 2*i*j] = false;
}
}
for(var i = 0; i < g; i++) ar[i] && r.push((i+o)*2+1);
return r;
}
var cs = n <= 1e6 ? 7500
: n <= 1e7 ? 60000
: 100000, // chunk size
cc = ~~(n/cs), // chunk count
xs = n % cs, // excess after last chunk
ar = Array(cs/2), // array used as map
result = [];
for(var i = 0; i < cc; i++) result = primeSieve(cs/2,i*cs/2,result);
result = xs ? primeSieve(xs/2,cc*cs/2,result) : result;
result[0] *=2;
return result;
}
var primes = [];
console.time(\"primes\");
primes = findPrimes(1000000000);
console.timeEnd(\"primes\");
console.log(primes.length);
I am not sure if it gets any better than this. I would love to hear your opinions.
回答6:
A number is a prime if it is not divisible by other primes lower than the number in question.
So this builds up a primes
array. Tests each new odd candidate n
for division against existing found primes
lower than n
. As an optimization it does not consider even numbers and prepends 2
as a final step.
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);
回答7:
To find prime numbers between 0 to n. You just have to check if a number x is getting divisible by any number between 0 - (square root of x). If we pass n and to find all prime numbers between 0 and n, logic can be implemented as -
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;
}
回答8:
Luchian\'s answer gives you a link to the standard technique for finding primes.
A less efficient, but simpler approach is to turn your existing code into a nested loop. Observe that you are dividing by 2,3,4,5,6 and so on ... and turn that into a loop.
Given that this is homework, and given that the aim of the homework is to help you learn basic programming, a solution that is simple, correct but somewhat inefficient should be fine.
回答9:
Using recursion combined with the square root rule from here, checks whether a number is prime or not:
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);
}
回答10:
Here\'s the fastest way to calculate primes in JavaScript, based on the previous prime value.
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 = 0, 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 faster than other alternatives published here, because:
- It aligns the loop limit to an integer, which works way faster;
- 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.
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>\"
);
}
回答11:
<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>
回答12:
Sieve of Eratosthenes. its bit look but its simple and it works!
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);
回答13:
Here\'s my stab at it.
Change the initial i=0
from 0 to whatever you want, and the the second i<100
from 100 to whatever to get primes in a different range.
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);
}
}
I tried it with 10000000
- it takes some time but appears to be accurate.
回答14:
Why to try deleting by 4 (and 6,8,10,12) if we already tried deleting by 2 ? Why to try deleting by 9 if already tried deleting by 3 ? Why to try deleting by 11 if 11 * 11 = 121 > 100 ? Why try deleting any odd number by 2 at all? Why try deleting any even above 2 by anything at all?
Eliminate dead tests and you\'ll get yourself a good code testing for primes below 100.
And your code is very far from being the worst code ever. Many many others would try dividing 100 by 99. But the absolute champion would generate all products of 2..96
with 2..96
to test whether 97 is among them. That one really is astonishingly inefficient.
Sieve of Eratosthenes of course is much better, and you can have one -- for the under 100s -- with no arrays of booleans (and no divisions too!):
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\"
回答15:
And this famous code from a famous JS Ninja
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));
回答16:
A list built using the new features of ES6, especially with generator.
Go to https://codepen.io/arius/pen/wqmzGp made in Catalan language for classes with my students. I hope you find it useful.
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);
回答17:
Using Sieve of Eratosthenes, source on Rosettacode
fastest solution: https://repl.it/@caub/getPrimes-bench
function getPrimes(limit) {
if (limit < 2) return [];
var sqrtlmt = limit**.5 - 2;
var nums = Array.from({length: limit-1}, (_,i)=>i+2);
for (var i = 0; i <= sqrtlmt; i++) {
var p = nums[i]
if (p) {
for (var j = p * p - 2; j < nums.length; j += p)
nums[j] = 0;
}
}
return nums.filter(x => x); // return non 0 values
}
document.body.innerHTML = `<pre style=\"white-space:pre-wrap\">${getPrimes(100).join(\', \')}</pre>`;
// for fun, this fantasist regexp way (very inefficient):
// Array.from({length:101}, (_,i)=>i).filter(n => n>1&&!/^(oo+)\\1+$/.test(\'o\'.repeat(n))
回答18:
First, change your inner code for another loop (for
and while
) so you can repeat the same code for different values.
More specific for your problem, if you want to know if a given n
is prime, you need to divide it for all values between 2 and sqrt(n). If any of the modules is 0, it is not prime.
If you want to find all primes, you can speed it and check n
only by dividing by the previously found primes. Another way of speeding the process is the fact that, apart from 2 and 3, all the primes are 6*k
plus or less 1.
回答19:
It would behoove you, if you\'re going to use any of the gazillion algorithms that you\'re going to be presented with in this thread, to learn to memoize some of them.
See Interview question : What is the fastest way to generate prime number recursively?
回答20:
Use following function to find out prime numbers :
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
}
回答21:
check the number is prime or not with JS function
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;
}
回答22:
Here is a way to test if number is prime number.
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;
}
回答23:
I modified Rinto\'s answer just for those who don\'t want to use the prompt method and just want to see the program print prime numbers . its working
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
}
}
回答24:
How about something like this.
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>\');
}
回答25:
This is my solution
//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));
回答26:
I have created a JSFiddle showing how it should work in a readable way,
idea is to have two functions isPrime and getPrimeNumbers to separate functionality, as well as using Math.pow and initial value of 2, as it should be always there, see the jsfiddle attached 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);
})();
};
回答27:
Here is my solution using Sieve of Eratosthenes method:
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);
回答28:
Here are the Brute-force iterative
method and Sieve of Eratosthenes
method to find prime numbers upto n. The performance of the second method is better than first in terms of time complexity
Brute-force iterative
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;
}
Sieve of Eratosthenes method
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);
});
}
}
回答29:
You can use this for any size of array of prime numbers. Hope this helps
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>
回答30:
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);
}