Вопрос:
Я пишу JavaScript для генерации простых чисел от 2 до 100. Однако он не работает и не может понять это.
ты поможешь мне, пожалуйста?
var array = new Array(100); for (var i=2 ; i<=array.length-1; i++) { if((i%2===0) || (i%3===0)) continue; document.writeln(i+»,»); }
Я изменил свой ответ, но теперь он не печатает 2 и 3; как я могу включить 2 & 3… результат:
5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97
Ответ №1function isPrime(num) { for ( var i = 2; i < num; i++ ) { if ( num % i === 0 ) { return false; } } return true; } function display(n) { var arr = [2]; for ( var i = 3; i < n; i+=2 ) { if ( isPrime(i) ) { arr.push(i); } } console.log(arr); // use arr result on your own } display(100);
ПРИМЕЧАНИЕ. Задайте параметр n в функции отображения и получите числа от 2 до n…
Проверьте JSFiddle
Обновление: обратите внимание, что приведенный выше сценарий верен, и я оставляю его, хотя добавив одну и ту же функцию с одной функциональностью:
function prime(n,flag) { ( typeof flag === «undefined» || flag === false ) ? flag = false : flag = true; function isPrime(num) { if ( num === 0 || num === 1 ) { return false; } for ( var i = 2; i < num; i++ ) { if ( num % i === 0 ) { return false; } } return true; } if ( flag ) { var arr = [2]; for ( var i = 3; i <= n; i+=2 ) { if ( isPrime(i) ) { arr.push(i); } } return arr; } else { return isPrime(n); } }
Объяснение: prime функция ожидает два параметра, первый из которых требуется, а второй – необязательный. Если указан только первый параметр, функция вернет true или false на основе числа, которое принадлежит или не соответствует простым. Если второй параметр указан как true (или любой другой тип, кроме undefined и false), функция вернет array простых чисел от 2 до n. Например:
console.log(prime(2)); // returns true ( 2 is prime ) console.log(prime(8)); // returns false ( 8 isn’t prime ) console.log(prime(100,true)); // returns [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] Ответ №2
Версия с использованием генераторов javascript:
function* take(length, iterable) { for (let x of iterable) { if (length <= 0) return; length—; yield x; } } function* primes() { let n = 2; while (true) { if (isPrime(n)) yield n; n++; } function isPrime(num) { for (var i = 2; i <= Math.sqrt(num); i++) { if (num % i === 0) { return false; } } return true; } } console.log([…take(4, primes())]); //[ 2, 3, 5, 7 ]Ответ №3
У вашего исходного кода есть многочисленные недостатки. Чтобы реализовать Сито Эратосфена, вам нужно добавить каждое число, которое вы найдете в массив, а затем проверить следующий премьер-кандидат на каждое основное, которое вы нашли до сих пор. Если кандидат не делится ни на один из простых чисел в массиве, то он является простым, и вы можете добавить его в свой массив простых чисел.
Здесь рабочая версия ( Демонстрация):
function start() { var array = [2, 3]; for (var i = 5; i <= 100; i += 2) { if (array.every(function(p) { return i % p; })) { array.push(i); } } var result = array.join(«,»); document.getElementById(«output»).innerHTML = result; } start();
Обратите внимание, что это зависит от Array.prototype.every который был введен в ECMAScript 5.
Ответ №4var enterNumber = prompt(«Enter number: «); for(var i=1; i<=enterNumber ;i++){ var isPrime = true; for(var j=2; j<i; j++){ if(i%j === 0){ isPrime = false; } } if(isPrime === true){ console.log(i); } } Ответ №5
У вас есть много способов добиться этого.
Вы были в основном на правильном пути, однако вы должны проверять каждое число, если оно делится на каждое задание, которое вы определили до сих пор:
var primes = [2],isPrime; for (var i=3;i<100;i+=2){ isPrime = true; // test the number you are examaning against // all the primes you found so far for (var j = 0;j<primes.length;j++){ if (i%primes[j]==0){ isPrime=false; break; } } if(isPrime){primes.push(i)} } console.log(primes);
Или вы можете использовать Сито Эратосфена, которое сортирует все числа, чтобы избежать дублирования тестов.
Истинная реализация SoE:
// initialize the array first var numbers = [], primes = [], maxNumber = 100; for(var i = 2;i<=maxNumber;i++){ numbers.push(i); } while(numbers.length){ primes.push(numbers.shift()); numbers = numbers.filter( function(i){return i%primes[primes.length-1]!=0} ); } console.log(primes);
Ответ №6
это может быть эффективным способом:
function calcPrimes(max){ var primes = []; for(var i=2; i<=max; i++){ var isPrime = true; for(var j=0; j<primes.length; j++){ var p = primes[j]; if( i % p === 0){ //it is divisible by another prime, so it not prime isPrime=false; break; } //you don’t need to check primes bigger than sqrt(i) if(p*p > i) break; } if(isPrime) primes.push(i); } console.log(JSON.stringify(primes)) console.log(primes.length) } calcPrimes(100); Ответ №7
Здесь приведен рабочий пример того, как генерировать неограниченное количество простых чисел, используя вариацию сита эратостхтенов. Это истинный SoE и не выполняет пробное деление, чтобы определить, является ли число простым. Это может показаться немного странным, но это потому, что он предназначен для работы без каких-либо ограничений.
<input type=button value=»Start» onClick=»do_cancel(); do_once()»> <input type=button value=»Stop» onClick=»do_cancel()»> <table id=»mytable»></table> <script> ‘use strict’; (function () { var ptable = document.getElementById(«mytable»); var prow = [2, 3]; function insertPrimeIntoTable(prime) { prow.push(prime); if( prow.length < 10 ) return false; var tr = document.createElement(‘tr’); for( var i = 0; i < prow.length; ++i ) { var cell = document.createElement(‘td’); cell.appendChild( document.createTextNode( prow[i] ) ); tr.appendChild( cell ); } ptable.appendChild( tr ); prow = []; return true; }; var factors = []; function insertPrimeIntoSieve( factor ) { var where = factor; while( factors[where] ) where += factor; /* while( factors.length < where ) factors.push(0); */ factors[ where ] = factor; } var primes = []; var a_prime = 3, a_squared_prime = 9, maybe_prime = 3; var canceller; function do_once() { var factor = factors[0]; maybe_prime += 2; if( factor ) { //if( 0 != (maybe_prime % factor) ) // throw «Unexpected remainder.»; insertPrimeIntoSieve( factor ); } else if( maybe_prime < a_squared_prime ) { insertPrimeIntoTable( maybe_prime ); primes.push( maybe_prime ); } else if( maybe_prime == a_squared_prime ) { insertPrimeIntoSieve( a_prime ); a_prime = primes.shift(); a_squared_prime = a_prime * a_prime; } else { throw «Critical math failure: Programmer or compiler is innumerate.»; } factors.shift(); canceller = window.setTimeout( do_once, 5 ); }; function do_cancel() { if( canceller ) window.clearTimeout( canceller ); canceller = null; } window.do_once = do_once; window.do_cancel = do_cancel; })(); </script> Ответ №8
Вы можете сделать это следующим образом:
Пример: http://jsfiddle.net/979gZ/
function inArray(needle, haystack) { var length = haystack.length; for(var i = 0; i < length; i++) { if(haystack[i] == needle) return true; } return false; } function isPrime(num) { //-n, 0, 1 not allowed if (num < 2) return false; //check for single digit primes if (inArray(num, [2, 3, 5, 7])) return true; //prime numbers end in 1, 3, 7 or 9 no matter how long they are if (!inArray(String(num).substr(-1), [1, 3, 7, 9])) return false; //if the number is divisible by 3 or 7 (very common) then it not prime if (num % 3 == 0 || num % 7 == 0) return false; /* * Now find all the numbers up to the square root of potential prime * number and test if they divide into it */ //the primes array holds prime numbers to test if they divide into num var primes = [2, 3, 5, 7]; var limit = Math.sqrt(num); for (var i = 11; i <= limit; i++) { //if the number is divisible by a prime number then it not prime var isPrime = true; for(var t = 0; t < primes; t++) { if (i % primes[t] == 0) { isPrime = false; break; } } //check if the increment goes into our number if (isPrime) { if (num % i == 0) return false; primes.push(i); } } //num is prime — divisible by itself and 1 only return true; } function start() { var max = 100; for (i = 2; i <= max; i++) { if(isPrime(i)) { console.log(i, «is a prime number»); } } } start(); Ответ №9function isPrime(num) { if (num % 2 == 0) { return false; } let n = Math.sqrt(num); for ( var i = 3; i <= n; i += 2 ) { if ( num % i === 0 ) { return false; } } return true; } function print(n) { var arr = [2]; for ( var i = 3; i < n; i+=2 ) { if ( isPrime(i) ) { arr.push(i); } } console.log(arr); } print(100); Ответ №10Please try this, var a = […Array(100).keys()]; var primeNumbers = a.map(v => { if (v % 2 === 0 || v % 3 === 0) { if (v === 2 || v === 3) { return v; } else { return; } } else { return v; } }); primeNumbers.filter(val => val); you will get 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97 Ответ №11
Я знаю, что этот вопрос задают в 2014 году, но на всякий случай, если OP или кто-то задается вопросом о том, как генерировать небольшие простые числа с помощью Javascript, я поделился небольшим кодом JS в https://github.com/HMaxF/generate-small-prime. -номер.
В моем MacBook Pro я могу генерировать все простые числа от 2 до 100 миллионов примерно за 25 секунд, но результат вашей машины будет отличаться.
Ответ №12
Я согласен с PSWG. Ваш оригинальный код имеет множество недостатков.
var prime = [2,3,5,7]; for(var x = 0; x < 100; x++){ var isPrime = prime.map(n => x%n > 0).filter(t => !t).length <= 0; if(isPrime || prime.includes(x)){ console.log(x); } }Ответ №13function printPrimes(num) { let sum = [] for(let i = 2; i<=num; i++) { if(check(i)) { sum.push(i) } } return sum } function check(num) { // function to check number is prime or not if(num <= 1 || typeof num !== ‘number’) { return false }else if(num ===2) { return true }else if (num%2 === 0) { return false } for(let i=3; i*i <= num;i +=2) { if(num%i === 0) { return false } } return true } console.log(printPrimes(100))Ответ №14
Просто используйте этот Java Script для простых чисел от 2 до нужного вам числа:
function primeFactorsTo(num) { var store = [], i, j, primes = []; for (i = 2; i <= num; ++i) { if (!store [i]) { primes.push(i); for (j = i << 1; j <= num; j += i) { store[j] = true; } } } return primes; } console.log(primeFactorsTo(200)); Ответ №15Ive Made the easiest Algorithm to solve this Problem Step 1 – Create a function to check a number is prime or not (PrimeFilter) . Step 2 – Create another function to print prime numbers smaller than given number , inside it declare an empty array . Step 3 – Loop from 2 ( first prime number ) to the given number , and pass every loop value to the function PrimeFilter ( It will check every loop value if its prime or not ) . Step 4 – If its a prime add it to the empty array . Thats it 🙂 function PrimeFilter(num){ if(num===0){ return false; } else if(num===1){ return false; } else if(num===2){ return true; } else { for(var i=2; i<num; i++){ if(num%i===0){ return false; } } return true; } } function UptoPrime(number){ var List =[]; for(var i=2; i<=number; i++){ if(PrimeFilter(i)){ List.push(i); } } console.log(List.join(‘ ‘)); } Ответ №16
со ссылкой на этот ответ это проверяет простые числа и печатает желаемое число без простых чисел между заданным диапазоном
const isPrime = num => { for(let i = 2; i < num; i++) if(num % i === 0) return false; return num > 1; } primes = [] ; for(let i = 2; i < max ; i ++) { if(isPrime(i)) { primes.push(i) } } console.log(primes); Ответ №17
Недавно работал с простыми числами и попал на эту страницу. Вот мое рабочее решение, использующее введите описание ссылки здесь алгоритм с оптимизацией 6k ± 1 и игнорируя все четные и делители 5.
Скопируйте и вставьте код как HTML. Печатает 1-е 1,000,000 простое число в 10 seconds прибл.
<!DOCTYPE html> <HTML> <HEAD> <meta charset=»utf-8″> <meta name=»viewport» content=»width=device-width, initial-scale=1″> <link rel=»stylesheet» href=»https://cdnjs.cloudflare.com/ajax/libs/bulma/0.7.5/css/bulma.min.css»> <script defer src=»https://use.fontawesome.com/releases/v5.3.1/js/all.js»></script> <BODY> <SCRIPT type=»text/javascript»> // The largest integer Java natively supports is 2^53-1, so these // routines are designed to work for *positive* integers up to that. // Currently the function check does the idiot proof to see only positive // integers (not too large) are passed to the other routines. // trial_divide(N,max) uses trial division to seek the smallest // prime divisor of N, returns 0 if none found. function trial_divide(N,max) { // Trial divides the positive integer N by the primes from 2 to max // Returns the first prime divisor found, or 0 if none found // Note: if N < max^2 is a prime, then N will be returned. if (N%2 == 0) return 2; if (N%3 == 0) return 3; // No need to go past the square root of our number var Stop = Math.min(Math.sqrt(N),max); // Okay, lets «wheel factor» alternately adding 2 and 4 var di=2; for(i=5; i<=Stop; i+=di, di=6-di) { if (N%i == 0) return i; }; if (N >= max*max) return 0; return N; } // modmult(a,b,N) finds a*b (mod N) where a, b, and N can be // up to (2^53-1)/2. Might up this to 2^53-1 eventually… function modadd(a,b,N) { // When the integers a, b satisfy a+b > 2^53-1, then (a+b)%N is wrong // so we add this routine to allow us to reach a, b = 2^53-1. if (a+b > 9007199254740991) { // Could reduce a and b (mod N) here, but assuming that has already been done // won’t hurt if not… subtract 2^52 from one, 2^52-1 from the other and the // add it back modulo N (MaxInt+1) var t = ( (a-4503599627370496) + (b-4503599627370495) )%N; return ( t + (9007199254740991 % N) ); } // Usual case: a + b is not too large: return ( (a+b)%N ); } function modmult(a,b,N) { if (a > N) a = a%N; if (b > N) b = b%N; if (a*b <= 9007199254740991) { return ((a*b)%N); } else { if (b > a) return modmult(b,a,N); // Right to left binary multiplication var t = 0; var f = a; while (b > 1) { if ((b & 1) == 1) t = modadd(t,f,N); b = Math.floor(b/2); f = modadd(f,f,N); }; t = modadd(t,f,N); return t; } } // modpow(a,exp,N) finds a^exp (mod N) where a, b, and N are // limited by modmult function modpow(a,exp,N) { if (exp == 0) return 1; // Right to left binary exponentiation var t = 1; var f = a; while (exp > 1) { if ((exp & 1) == 1) { // if exponent is odd t = modmult(t,f,N); } exp = Math.floor(exp/2); f = modmult(f,f,N); }; t = modmult(t,f,N); return t; } // SPRP(N,a) checks if N (odd!) is a strong probable prime base a // (returns true or false) function SPRP(N,a) { var d = N-1; s = 1; // Assumes N is odd! while ( ((d=d/2) & 1) == 0) s++;// Using d>>1 changed the sign of d! // Now N-1 = d*2^s with d odd var b = modpow(a,d,N); if (b == 1) return true; if (b+1 == N) return true; while (s— > 1) { b = modmult(b,b,N); if (b+1 == N) return true; } return false; } // The idiot proofing, answer returning script function check(e){ if (e.hasAttribute(«disabled»)) return; var start = performance.now(); var TrialLimit = 1300; // Should be bigger, like 10000 var N = document.getElementById(«primenumbercheck»).value; var Result = «Unknown error»; var a; if (N > 9007199254740991) { Result = «Sorry, this routine will only handle integers below 9007199254740991.»; } else if (N == 1) { Result = «The number 1 is neither prime or composite (it the multiplicative identity).»; } else if (N < 1) { Result = «We usually restrict the terms prime and composite to positive integers»; } else if (N != Math.floor(N)) { Result = «We usually restrict the terms prime and composite to positive integers»; } else { // Okay, N is of a resonable size, lets trial divide window.status = «Trial dividing » + N + » to » + TrialLimit + «.»; i = trial_divide(N,TrialLimit); if (i > 0 && i != N) { Result = N+» is not a prime! It is «+i+» * «+N/i; } else if (N < TrialLimit*TrialLimit) { Result = N+» is a (proven) prime!»; } else if ( SPRP(N,a=2) && SPRP(N,a=3) && SPRP(N,a=5) && SPRP(N,a=7) && SPRP(N,a=11) && SPRP(N,a=13) && SPRP(N,a=17)) { // Some of these tests are unnecessary for small numbers, but for // small numbers they are quick anyway. if (N < 341550071728321) { Result = N + » is a (proven) prime.»; } else if (N == 341550071728321) { Result = N+» is not a prime! It is 10670053 * 32010157.»; } else { Result = N + » is probably a prime (it is a sprp bases 2, 3, 5, 7, 11, 13 and 17).»; }; } else { Result = N+» is (proven) composite (failed sprp test base «+a+»).»; }; }; var end = performance.now(); var timeTaken = end — start; window.status= «Done!»; // here so says done when present alert box var x = document.getElementsByClassName(«primecheck»); x[0].innerHTML = Result; setTimer(timeTaken); } function generate(e){ if (e.hasAttribute(«disabled»)) return; var start = performance.now(); var x = document.getElementsByClassName(«primelist»); var N = document.getElementById(«primenumberlist»).value; var i = 2; var Result = «2, «; var currentInt = 3; var possiblePrime; if (N == 2) Result = Result + currentInt + «, «; else { while (i < N) { possiblePrime = false; if(currentInt == 3) { Result = Result + currentInt + «, «; possiblePrime = false; } else if(currentInt % 5 == 0 && currentInt > 5) { possiblePrime = false; } else if(currentInt % 6 == 1 || currentInt % 6 == 5) possiblePrime = true; if(possiblePrime) { if(trial_divide(currentInt,Math.ceil(Math.sqrt(currentInt))) == currentInt) { Result = Result + currentInt + «, «; i++; } } currentInt = currentInt + 2; } } var end = performance.now(); var timeTaken = end — start; x[0].innerHTML = Result.substring(0, Result.length — 2); setTimer(timeTaken); } function setTimer(timeTaken) { var timerElement = document.getElementsByClassName(«timeElapsed»)[0]; var timerPreText = «Time Elapsed: «; var duration = convertMS(timeTaken); timerPreText = timerPreText + duration.day + » days: » + duration.hour + » hours: » + duration.minute + » minutes: » + duration.seconds + » seconds» + «: » + duration.milliseconds + » milliseconds»; timerElement.innerHTML = timerPreText; } function isNumberKey(evt) { var charCode = (evt.which) ? evt.which : event.keyCode if (charCode > 31 && (charCode < 48 || charCode > 57)) return false; return true; } function convertMS( milliseconds ) { var day, hour, minute, seconds, milliseconds; seconds = Math.floor(milliseconds / 1000); milliseconds = milliseconds — (seconds * 1000); milliseconds = milliseconds.toFixed(2); minute = Math.floor(seconds / 60); seconds = seconds % 60; hour = Math.floor(minute / 60); minute = minute % 60; day = Math.floor(hour / 24); hour = hour % 24; return { day: day, hour: hour, minute: minute, seconds: seconds, milliseconds: milliseconds }; } function checkInput(input, buttonId) { var name = input.value; var cansubmit = (name.length > 0); if (cansubmit) { document.getElementById(buttonId).removeAttribute(«disabled»); } else { document.getElementById(buttonId).setAttribute(«disabled», null); } }; </SCRIPT> <article class=»message is-success timerDiv» style=»visibility: visible;»> <div class=»message-body»> <p class=»timeElapsed»>Time elapsed will be shown here!</p> </div> </article> <article class=»message is-primary»> <div class=»message-body»> <strong class=»title»>Check prime number</strong> <div class=»content» style=»margin-top: 10px;»> <div><input id=»primenumbercheck» class=»input is-rounded» type=»text» placeholder=»Enter the number you wanna check…» style=»max-width: 25%;» onkeypress=»return isNumberKey(event)» onkeyup=»checkInput(this, ‘primenumbercheckButton’)»> <a class=»button is-link is-rounded» onclick=»check(this)» id=»primenumbercheckButton» disabled>Check</a></div> </div> </div> </article> <div class=»container is-fullhd»> <div class=»notification primecheck»> Prime check goes here! </div> </div> <article class=»message is-primary»> <div class=»message-body»> <strong class=»title»>List prime numbers</strong> <div class=»content» style=»margin-top: 10px;»> <div><input id=»primenumberlist» class=»input is-rounded» type=»text» placeholder=»Enter the number of prime numbers you wanna generate…» style=»max-width: 35%;» onkeypress=»return isNumberKey(event)» onkeyup=»checkInput(this, ‘primenumberlistButton’)»> <a class=»button is-link is-rounded» onclick=»generate(this)» id=»primenumberlistButton» disabled>List</a></div> </div> </div> </article> <div class=»container is-fullhd»> <div class=»notification primelist»> Prime list goes here! </div> </div> </div> </BODY> </HEAD> </HTML>
