Проблемы с JavaScript: простые числа и простые числа Софи Жермен
22 декабря 2022 г.Простые числа
Что такое простые числа?
Простое число — это целое число больше 1, которое нельзя точно разделить ни на какое целое число, кроме самого себя и 1 (например, 2, 3, 5, 7, 11).
Число 5 является простым числом, потому что его делители равны только 1 и 5.
Число 4 не простое число, потому что его делители равны 1, 2 и 4.
Давайте создадим функцию, которая будет возвращать true, если строка является простым числом, и false, если число не является простым. сильный>.
isPrime(3); // true
isPrime(9); // false
Давайте создадим функцию
function isPrime(num) {
}
Простое число — это число больше 1. Таким образом, число меньше 1 не является простым числом.
function isPrime(num) {
if (num <= 1) return false;
}
isPrime(-5); // false
оператор по модулю используется для получения остатка после деления. Мы собираемся проверить, можно ли разделить число на другие множители (кроме 1 и самого себя) без остатка.
function isPrime(num) {
if (num <= 1) return false;
for (let i=2; i<num; i++) {
if (num%i !== 0) return false;
}
return true;
}
Помните, что 2 – это простое число
.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
Что, если у нас будет огромное количество?
isPrime(56669900033);
Наша функция будет работать медленнее. Мы можем сократить процесс, используя квадратный корень. Например,
число 121. Квадратный корень из 121 равен 11. Это означает, что 121 не является простым числом, потому что простое число можно разделить поровну только на себя и на 1. Таким образом, вместо итерации от 2 до 121, мы можем просто выполнить итерацию до 11 включительно, квадратного корня из 121.
Math.sqrt() найти квадратный корень числа.
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
Софи Жермен Простые числа
Если p и 2p+1 простые, то p является простым числом Софи Жермен. Например, 2, 3, 5, 11, 23, 29, 41, 53, 83, 89…
5 — это простое число и 5*2+1=11
11 также является простым числом. Таким образом, и 5, и 11 являются простыми числами Софи Жермен.
Давайте создадим функцию, которая будет возвращать массив простых чисел Софи Жермен от 2 до n.
Мы будем использовать нашу функцию isPrime() из предыдущего примера, чтобы проверить, является ли число простым.
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]
https://www.youtube.com/watch?v=XOgA8s2y7-Y/ ?embedable=true
Надеюсь, это было вам полезно!
Оригинал