Ik probeer de Codewars-uitdaging te voltooien waarin je wordt gevraagd te controleren of een getal een priemgetal is . Om welke reden dan ook, mijn oplossing lijkt niet te werken voor het kwadraat van oneven priemgetallen (bijv. 9
geeft true
terug in plaats van false
).
function isPrime(num) {
if (num === 2) {
return true;
} else if (num > 1) {
for (var i = 2; i < num; i++) {
if (num % i !== 0) {
return true;
} else if (num === i * i) {
return false
} else {
return false;
}
}
} else {
return false;
}
}
console.log(isPrime(121));
Antwoord 1, autoriteit 100%
Zo eenvoudig mogelijk:
function isPrime(num) {
for(var i = 2; i < num; i++)
if(num % i === 0) return false;
return num > 1;
}
Met de ES6-syntaxis:
const isPrime = num => {
for(let i = 2; i < num; i++)
if(num % i === 0) return false;
return num > 1;
}
U kunt ook de complexiteit van het algoritme verlagen van O(n)
naar O(sqrt(n))
als u de lus uitvoert tot de vierkantswortel van een getal :
const isPrime = num => {
for(let i = 2, s = Math.sqrt(num); i <= s; i++)
if(num % i === 0) return false;
return num > 1;
}
Antwoord 2, autoriteit 15%
Een kleine suggestie hier, waarom wil je de lus uitvoeren voor hele n getallen?
Als een getal een priemgetal is, heeft het 2 factoren (1 en het getal zelf).
Als het geen priemgetal is, hebben ze 1, nummer zelf en meer, je hoeft de lus niet tot het nummer te lopen, misschien kun je overwegen om het tot de vierkantswortel van het nummer te laten lopen.
Je kunt het ofwel doen volgens de primaire logica van euler.
Controleer het volgende fragment:
function isPrime(num) {
var sqrtnum=Math.floor(Math.sqrt(num));
var prime = num != 1;
for(var i=2; i<sqrtnum+1; i++) { // sqrtnum+1
if(num % i == 0) {
prime = false;
break;
}
}
return prime;
}
De complexiteit is nu O(sqrt(n))
Voor meer informatie
Waarom controleren we tot de vierkantswortel van een priemgetal om te bepalen of het een priemgetal is?
Hopelijk helpt het
Antwoord 3, autoriteit 7%
function isPrime(num) { // returns boolean
if (num <= 1) return false; // negatives
if (num % 2 == 0 && num > 2) return false; // even numbers
const s = Math.sqrt(num); // store the square to loop faster
for(let i = 3; i <= s; i += 2) { // start from 3, stop at the square, increment in twos
if(num % i === 0) return false; // modulo shows a divisor was found
}
return true;
}
console.log(isPrime(121));
Dank aan Zeph voor het herstellen van mijn fouten.
Antwoord 4, autoriteit 6%
Coole versie:
const isPrime = n => ![...Array(n).keys()].slice(2).map(i => !(n%i)).includes(true) && ![0,1].includes(n)
Antwoord 5, autoriteit 3%
// A list prime numbers
function* Prime(number) {
const infinit = !number && number !== 0;
const re = /^.?$|^(..+?)\1+$/;
let actual = 1;
while (infinit || number-- ) {
if(!re.test('1'.repeat(actual)) == true) yield actual;
actual++
};
};
let [...primers] = Prime(101); //Example
console.log(primers);
Antwoord 6, autoriteit 3%
function isPrimeNumber(n) {
for (var i = 2; i < n; i++) { // i will always be less than the parameter so the condition below will never allow parameter to be divisible by itself ex. (7 % 7 = 0) which would return true
if(n % i === 0) return false; // when parameter is divisible by i, it's not a prime number so return false
}
return n > 1; // otherwise it's a prime number so return true (it also must be greater than 1, reason for the n > 1 instead of true)
}
console.log(isPrimeNumber(1)); // returns false
console.log(isPrimeNumber(2)); // returns true
console.log(isPrimeNumber(9)); // returns false
console.log(isPrimeNumber(11)); // returns true
Antwoord 7, autoriteit 3%
Priemgetallen hebben de vorm 6f ± 1, met uitzondering van 2 en 3 waarbij f een willekeurig geheel getal is
function isPrime(number)
{
if (number <= 1)
return false;
// The check for the number 2 and 3
if (number <= 3)
return true;
if (number%2 == 0 || number%3 == 0)
return false;
for (var i=5; i*i<=number; i=i+6)
{
if (number%i == 0 || number%(i+2) == 0)
return false;
}
return true;
}
Tijdcomplexiteit van de oplossing: O (SQRT (N))
8, Autoriteit 2%
Ik denk dat deze vraag een recursief oplossing heeft:
// Preliminary screen to save our beloved CPUs from unneccessary labour
const isPrime = n => {
if (n === 2 || n === 3) return true;
if (n < 2 || n % 2 === 0) return false;
return isPrimeRecursive(n);
}
// The recursive function itself, tail-call optimized.
// Iterate only over odd divisors (there's no point to iterate over even ones).
const isPrimeRecursive = (n, i = 3, limit = Math.floor(Math.sqrt(n))) => {
if (n % i === 0) return false;
if (i >= limit) return true; // Heureka, we have a prime here!
return isPrimeRecursive(n, i += 2, limit);
}
// Usage example
for (i = 0; i <= 50; i++) {
console.log(`${i} is ${isPrime(i) ? `a` : `not a` } prime`);
}
9, Autoriteit 2%
function isPrime(num) {
var prime = num != 1;
for(var i=2; i<num; i++) {
if(num % i == 0) {
prime = false;
break;
}
}
return prime;
}
10, Autoriteit 2%
een van de kortste versie
isPrime=(n)=>[...Array(n-2)].map((_,i)=>i+2).filter(i=>n%i==0).length==0
Antwoord 11, autoriteit 2%
Ik zou het als volgt doen:
const isPrime = (num) => num < 10 ? [2, 3, 5, 7].includes(num) : ![2, 3, 5, 7].some(i => !(num % i));
Antwoord 12
u kunt onderstaande code in javascript gebruiken om te controleren of het nummer priemgetal is of niet.
Het zal geen iteratie verminderen en het resultaat snel krijgen.
function testPrime(num) {
var isPrime = true;
if (num >= 2) {
if(num == 2 || num == 3){
isPrime = true;
}
else if (num % 2 == 0) {
isPrime = false;
}
else {
for (i = 3; i <= Math.floor(Math.sqrt(num)); i += 2) {
if (num % i == 0) {
isPrime = false;
break;
}
}
}
}
else {
isPrime = false;
}
return isPrime;
}
//testPrime(21)
vals
Antwoord 13
Ik denk dat een betere manier om een priemgetal te vinden is met deze logica:
var p=prompt("input numeric value","10"); // input your number
for(j=2;j<p;j++){
if(isPrimes(j)){
document.write(j+", "); // for output the value
} // end if
}// end for loop
function isPrimes(n) {
var primes = true;// let prime is true
for (i=2;i<n;i++) {
if(n%i==0) {
primes= false; // return prime is false
break; // break the loop
}// end if inner
}// end inner loop
return primes; // return the prime true or false
}// end the function
Antwoord 14
Je kunt deze proberen
function isPrime(num){
// Less than or equal to 1 are not prime
if (num<=1) return false;
// 2 and 3 are prime, so no calculations
if (num==2 || num==3 ) return true;
// If mod with square root is zero then its not prime
if (num % Math.sqrt(num)==0 ) return false;
// Run loop till square root
for(let i = 2, sqrt = Math.sqrt(num); i <= sqrt; i++) {
// If mod is zero then its not prime
if(num % i === 0) return false;
}
// Otherwise the number is prime
return true;
}
for(let i=-2; i <= 35; i++) {
console.log(`${i} is${isPrime(i) ? '' : ' not'} prime`);
}
Antwoord 15
Misschien nuttig voor sommige mensen: een implementatie van de Miller Rabin-primaliteitstest. Werkt voor alle positieve gehele getallen kleiner dan Number.MAX_SAFE_INTEGER.
Probeer JSFiddle: https://jsfiddle.net/4rxhas2o/
let unsafeToSquare = Math.floor(Math.sqrt(Number.MAX_SAFE_INTEGER))
function addMod(a, b, m) {
// Returns (a + b) % m
let sum = a + b
let result = sum % m
if (sum < Number.MAX_SAFE_INTEGER)
return result
let signature = ((a % 8) + (b % 8)) % 8
let sumMod = sum % 8
for (let i = -2; i <= 2; ++i) {
if ((sumMod + i) % 8 === signature) {
let ret = result + i
if (ret > m)
ret = (result - m) + i // prevent overflow
return ret
}
}
}
function mulMod(a, b, m) {
if (m === 0)
return 0
let prod = a * b
if (prod < Number.MAX_SAFE_INTEGER)
return prod % m
let y = 0
let result = a
while (b > 1) {
if (b % 2 === 0) {
result = addMod(result, result, m)
b /= 2
} else {
y = addMod(result, y, m)
result = addMod(result, result, m)
b = (b - 1) / 2
}
}
return addMod(result, y, m)
}
function squareMod(b, m) {
// Computes (b * b % m)
return mulMod(b, b, m)
}
function expModLargeB(b, exponent, m) {
let y = 1
while (exponent > 1) {
if (exponent % 2 === 0) {
b = squareMod(b, m)
exponent /= 2
} else {
y = mulMod(y, b, m)
b = squareMod(b, m)
exponent = (exponent - 1) / 2
}
}
return mulMod(b, y, m)
}
function expMod(b, exponent, m) {
if (exponent === 0)
return 1
if (b >= unsafeToSquare || m >= unsafeToSquare) {
return expModLargeB(b, exponent, m)
}
let y = 1
while (exponent > 1) {
if (exponent % 2 === 0) {
b *= b
b %= m
exponent /= 2
} else {
y *= b
b *= b
y %= m
b %= m
exponent = (exponent - 1) / 2
}
}
return (b * y) % m
}
function _isPrimeTrialDivision(p) {
let sqrtP = Math.ceil(Math.sqrt(p))
for (let i = 23; i <= sqrtP + 1; i += 2) {
if (p % i === 0)
return false
}
return true
}
function _isProbablePrimeMillerRabin(p, base=2) {
let pm1 = p - 1
let pm1div = pm1
let d, r = 0
while (true) {
if (pm1div % 2 === 0) {
pm1div /= 2
r++
} else {
d = pm1div
break
}
}
let x = expMod(base, d, p)
if (x === 1 || x === pm1)
return true
for (let i = 0; i < r - 1; ++i) {
x = squareMod(x, p)
if (x === pm1)
return true
}
return false
}
function _isPrimeLarge(p) {
let bases
if (p < 2047)
bases = [2]
else if (p < 1373653)
bases = [2, 3]
else if (p < 9080191)
bases = [31, 73]
else if (p < 25326001)
bases = [2, 3, 5]
else if (p < 3215031751)
bases = [2, 3, 5, 7]
else if (p < 4759123141)
bases = [2, 7, 61]
else if (p < 1122004669633)
bases = [2, 13, 23, 1662803]
else if (p < 2152302898747)
bases = [2, 3, 5, 7, 11]
else if (p < 3474749660383)
bases = [2, 3, 5, 7, 11, 13]
else if (p < 341550071728321)
bases = [2, 3, 5, 7, 11, 13, 17]
else
bases = [2, 3, 5, 7, 11, 13, 17, 19, 23]
return bases.every(base => _isProbablePrimeMillerRabin(p, base))
}
let smallPrimes = [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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223]
function isPrime(p) {
if (!Number.isInteger(p) || p < 2)
return false
// Test for small primes
for (let i = 0; i < smallPrimes.length; ++i) {
let prime = smallPrimes[i]
if (p === prime)
return true
if (p % prime === 0)
return false
}
if (p < 150) {
return _isPrimeTrialDivision(p)
} else {
return _isPrimeLarge(p)
}
}
const tests = [1, 2, 3, 10, 100, 100019, 10000000019, 100000000003, 10000000000037]
let start = performance.now()
tests.forEach(test => {
console.log(`${test} is ${ isPrime(test) ? "" : "not " }prime`)
})
let end = performance.now()
console.log("Tests completed in " + (end - start) + " ms.")
Antwoord 16
U probeert te veel voorwaarden te controleren. er is slechts één lus nodig om te controleren op een priemgetal.
function isPrime(num){
if(num==2)
return true;
for(i=2;i<Math.sqrt(num);i++) // mathematical property-no number has both of its factors greater than the square root
{
if(num % i==0)
return false; // otherwise it's a prime no.
}
return true;
}
Je moet elk nee overwegen. een prime nr. tenzij het deelbaar is door een nr. kleiner dan of gelijk aan de vierkantswortel.
Uw oplossing heeft een return-statement voor elk geval, dus het stopt de uitvoering voordat het zou moeten. Het controleert geen enkel nummer meer dan één keer. Het geeft een verkeerd antwoord voor meerdere gevallen– 15,35.. elke nee. dat is vreemd.
Antwoord 17
Het ziet eruit als uw eerste if-statement binnen het eerste ‘if’-statement in de for-lus. Omdat als num = 9 en i = 2, 9% i !== 0 maar 9 geen priemgetal is, want bij de volgende iteratie waar i = 3, 9% i === 0.
Hier zou mijn antwoord op die vraag zijn.
var isPrime = function(n) {
if(typeof n !== 'number' || n <= 1 || n % 1 !== 0){
return false;
}
for(var i = 2; i <= Math.sqrt(n); i += 1){
if(n % i === 0){
return false;
}
}
return true;
};
De eerste if-instructie vangt de randgevallen op. De for-lus controleert vervolgens van 2 tot de vierkantswortel van n vanwege de wiskundige eigenschap waarbij geen enkel getal beide factoren groter heeft dan de vierkantswortel van dat getal.
Hopelijk helpt dit!
Antwoord 18
Dit is denk ik efficiënter om priemgetal te controleren:
function prime(num){
if(num == 1) return true;
var t = num / 2;
var k = 2;
while(k <= t) {
if(num % k == 0) {
return false
} else {
k++;
}
}
return true;
}
console.log(prime(37))
19
Eenvoudige versie:
function isPrime(num) {
if (num <= 1) {
return false;
} else {
for (var i = 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;
}
}
console.log(isPrime(9));
20
Dit is hoe ik het zou doen:
function isPrime(num) {
if(num < 2) return false;
if(num == 2) return true;
for(var i = 2; i < num; i++) {
if(num % i === 0) return false;
}
return true;
}
21
Zeer eenvoudig
const isPrime = num => {
for (var i = 2; i < num; i++) if (num % i == 0) return false;
return num >= 2;
}
22
function isAPrimeNumber(num){
var counter = 0;
//loop will go k equals to $num
for (k = 1; k <= num; k++) {
//check if the num is divisible by itself and 1
// `%` modulus gives the reminder of the value, so if it gives the reminder `0` then it is divisible by the value
if (num % k == 0) {
//increment counter value 1
counter = counter + 1;
}
}
//if the value of the `counter is 2` then it is a `prime number`
//A prime number is exactly divisible by 2 times only (itself and 1)
if (counter == 2) {
return num + ' is a Prime Number';
}else{
return num + ' is nota Prime Number';
}
}
Bel nu de functie isAPrimeNumber()
aan door een waarde door te geven.
var resp = isAPrimeNumber(5);
console.log(resp);
Uitvoer:
5 is a Prime Number
Antwoord 23
function isPrime(num) {
if(num < 2) return false;
for (var i = 2; i <= num/2; i++) {
if(num%i==0)
return false;
}
return true;
}
Als we het priemgetal tussen twee getallen willen, hoeven we alleen deze code toe te voegen
for(var i = 0; i < 100; i++){
if(isPrime(i))
console.log(i);
}
Antwoord 24
Aangevinkte oplossing Ihor Sakaylyuk gebruiken
const isPrime = num => {
for(let i = 2, s = Math.sqrt(num); i <= s; i++)
if(num % i === 0) return false;
return num !== 1 && num !== 0;
}
Geeft in console
isPrime( -100 )
waar
const isPrime = num => {
// if not is_number num return false
if (num < 2) return false
for(let i = 2, s = Math.sqrt(num); i <= s; i++) {
if(num % i === 0) return false
}
return true
}
Geeft in console
isPrime( 1 )
valsisPrime( 100 )
valsisPrime( -100 )
vals
Eerste 6 priemgetallen? 2 3 5 7 11 13 ?
isPrime( 1 )
valsisPrime( 2 )
waar // Prime 1isPrime( 3 )
waar // Prime 2isPrime( 4 )
valsisPrime( 5 )
waar // Prime 3isPrime( 6 )
valsisPrime( 7 )
waar // Prime 4isPrime( 8 )
valsisPrime( 9 )
valsisPrime( 10 )
valsisPrime( 11 )
waar // Prime 5isPrime( 12 )
valsisPrime( 13 )
waar // Prime 6
Antwoord 25
Dit antwoord is gebaseerd op het antwoord van Ihor Sakaylyuk. Maar in plaats van alle getallen te controleren, controleer ik alleen de oneven getallen. Hierdoor heb ik de tijdscomplexiteit van de oplossing teruggebracht tot O(sqrt(n)/2).
function isPrime(num) {
if (num > 2 && num % 2 === 0) return false;
for (var i = 3; i < Math.sqrt(num); i += 2) {
if (num % i === 0) return false;
}
return num > 1;
}
Antwoord 26
function isPrime(n){
if (isNaN(n) || !isFinite(n) || n%1 || n<2) {
return false;
}
if (n%2==0){
return (n==2);
}
var sqrt = Math.sqrt(n);
for (var i = 3; i < sqrt; i+=2) {
if(n%i == 0){
return false;
}
}
return true;
}
Antwoord 27
Mijn oplossing,
function isPrimeNumber(number){
if(number <= 1) return false;
if(number <= 3) return true;
for(let i = 2; i < 9; i++) {
if(number === i) continue;
if(number % i === 0 ) return false;
}
return true;
}
for(let i = 0; i <= 100; i++){
if (isPrimeNumber(i)) console.log(i);
}
Antwoord 28
Dit berekent het kwadraat anders en slaat even getallen over.
const isPrime = (n) => {
if (n <= 1) return false;
if (n === 2) return true;
if (n % 2 === 0) return false;
//goto square root of number
for (let i = 3, s = n ** 0.5; i < s; i += 2) {
if (n % i == 0) return false;
}
return true;
};
Antwoord 29
Dit is een betrouwbaardere oplossing als je n priemgetallen wilt vinden.
function findPrime(n) {
const primes = [];
loop1:
for (let j = 0; primes.length < n; j++) {
loop2:
for(let i = 2; i < j; i++){
if(j % i === 0){
continue loop1;
}
}
if(j>1) primes.push(j);
}
console.log(primes);
}
findPrime(5);