Thử thách JavaScript: Số nguyên tố & Số nguyên tố Sophie Germain

Số nguyên tố

Số nguyên tố là gì?

Số nguyên tố là số nguyên lớn hơn 1 không thể chia hết cho bất kỳ số nguyên nào khác ngoài chính nó và 1 (ví dụ: 2, 3, 5, 7, 11).

Số 5 là số nguyên tố vì chỉ có 2 ước là 1 và 5.

Số 4 không phải là số nguyên tố vì các ước của nó là 1, 2 và 4.

Hãy tạo một hàm sẽ trả về true nếu chuỗi là số nguyên tố và trả về false nếu một số không phải là số nguyên tố .

 isPrime(3); // true isPrime(9); // false

Hãy tạo một chức năng

 function isPrime(num) { }

Số nguyên tố là số lớn hơn 1. Vậy số nhỏ hơn 1 không phải là số nguyên tố.

 function isPrime(num) { if (num <= 1) return false; }

 isPrime(-5); // false

Toán tử modulo được sử dụng để lấy phần dư sau khi chia. Chúng ta sẽ kiểm tra xem num có thể được chia thành các thừa số khác (ngoại trừ 1 và chính nó) mà không để lại phần dư hay không.

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

Hãy nhớ rằng 2 là một số nguyên tố.

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

 isPrime(5); //true isPrime(9); //false

Nếu chúng ta có một số lượng lớn thì sao?

 isPrime(56669900033);

Chức năng của chúng tôi sẽ chạy chậm hơn. Chúng ta có thể rút ngắn quá trình bằng cách sử dụng căn bậc hai. Ví dụ,

số 121. Căn bậc hai của 121 là 11 . Điều này có nghĩa là 121 không phải là số nguyên tố , vì một số nguyên tố chỉ có thể chia hết cho chính nó và 1. Vì vậy, thay vì lặp từ 2 đến 121 , chúng ta chỉ có thể lặp đến và bao gồm 11 , căn bậc hai của 121 .

Math.sqrt() tìm căn bậc hai của một số.

 function isPrime(num) { if (num <= 1) return false; if (num === 2) return true; let numSqrt = Math.sqrt(num); for (let i=2; i<=numSqrt; i++) { if (num%i === 0) return false; } return true; }

 isPrime(5); //true isPrime(121); //false

Sophie Germain Số Nguyên Tố

Nếu cả p và 2p+1 đều là số nguyên tố thì p là số nguyên tố Sophie Germain . Ví dụ: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89…

5 là số nguyên tố và 5*2+1=11

11 cũng là một số nguyên tố . Vì vậy, cả 5 và 11 đều là số nguyên tố Sophie Germain.

Hãy tạo một hàm sẽ trả về một mảng các số nguyên tố Sophie Germain từ 2 đến n.

Chúng ta sẽ sử dụng hàm isPrime() từ ví dụ trước để kiểm tra xem số đó có phải là số nguyên tố hay không.

 function getGermainPrimes(n) { let result = []; // an array of Sophie Germain prime numbers (our result) for (let i = 0; i <= n; i++) { if (isPrime(i) && isPrime(i*2 + 1)) { //if both i and 2i+1 are prime result.push(i); } } return result; }

 getGermainPrimes(100); // [2, 3, 5, 11, 23, 29, 41, 53, 83, 89]

Tôi hy vọng bạn tìm thấy điều này hữu ích!