Số nguyên tố JavaScript

Một số nguyên lớn hơn 1 được gọi là số nguyên tố nếu nó không thể chia không dư cho bất kỳ số nào ngoại trừ 1 và chính nó

Nói cách khác, n > 1 là số nguyên tố nếu nó không thể chia hết cho bất kỳ thứ gì ngoại trừ 1 và n

Ví dụ, 5 là số nguyên tố, bởi vì nó không thể chia không có phần dư cho 2, 3 và

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // for each i...

  for (let j = 2; j < i; j++) { // look for a divisor..
    if (i % j == 0) continue nextPrime; // not a prime, go next i
  }

  alert( i ); // a prime
}

Viết đoạn mã xuất ra các số nguyên tố trong khoảng từ 2 đến n

Đối với

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // for each i...

  for (let j = 2; j < i; j++) { // look for a divisor..
    if (i % j == 0) continue nextPrime; // not a prime, go next i
  }

  alert( i ); // a prime
}

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // for each i...

  for (let j = 2; j < i; j++) { // look for a divisor..
    if (i % j == 0) continue nextPrime; // not a prime, go next i
  }

  alert( i ); // a prime
}

P. S. Mã phải hoạt động cho bất kỳ n nào, không được điều chỉnh khó cho bất kỳ giá trị cố định nào

Có nhiều thuật toán cho nhiệm vụ này

Hãy sử dụng một vòng lặp lồng nhau

For each i in the interval {
  check if i has a divisor from 1..i
  if yes => the value is not a prime
  if no => the value is a prime, show it
}

Mã sử ​​dụng nhãn

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // for each i...

  for (let j = 2; j < i; j++) { // look for a divisor..
    if (i % j == 0) continue nextPrime; // not a prime, go next i
  }

  alert( i ); // a prime
}

Có rất nhiều không gian để tối ưu hóa nó. Chẳng hạn, chúng ta có thể tìm các ước số từ 2 đến căn bậc hai của

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // for each i...

  for (let j = 2; j < i; j++) { // look for a divisor..
    if (i % j == 0) continue nextPrime; // not a prime, go next i
  }

  alert( i ); // a prime
}

Gần như chắc chắn rằng tại một thời điểm nào đó trong quá trình học viết mã của bạn, bạn sẽ được yêu cầu viết một số loại hàm liên quan đến các số nguyên tố. Đây là một bài tập phổ biến trong các chương trình đào tạo lập trình và đôi khi còn xuất hiện trong các cuộc phỏng vấn xin việc

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

Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có ước là 1 và chính nó. Tức là nó chỉ chia hết cho 1 và chính nó

Số tự nhiên là các số nguyên dương như 1, 5, 201, 229999, v.v. Số 0, phân số, số thập phân, số âm không phải là số tự nhiên

Số 5 là số nguyên tố vì thừa số DUY NHẤT của nó là 1 và 5. Không còn cách nào khác để ‘tạo ra’ số 5

Số 4 không phải là số nguyên tố vì 2 x 2 cũng cho ta 4

Số 20 không phải là số nguyên tố vì 5 x 4 cũng cho ta 20, cũng như 2 x 10

Các số nguyên tố không bao giờ chẵn (trừ 2)

Một trong những cách nhanh nhất để kiểm tra xem một số có phải là số nguyên tố hay không là kiểm tra xem nó có phải là số chẵn hay không. Nếu một số có thể chia hết cho 2 mà không để lại số dư thì nó không còn thỏa mãn định nghĩa về số nguyên tố — một số chỉ có thể chia hết cho 1 và chính nó

Trong JavaScript, chúng ta có thể kiểm tra các số chẵn bằng cách sử dụng toán tử modulo (%)

Toán tử modulo trả về phần còn lại sau khi một số nguyên được chia cho một số khác
Ví dụ 12 % 5 trả về 2
Và 59% 5 trả về 4

Nếu bạn chia một số nguyên cho 2 và phần còn lại là 0, chúng tôi biết rằng số nguyên đó là một số chẵn

Ví dụ 10 % 2 = 0
Và 2200% 2 = 0

trong JavaScript nó sẽ giống như thế này
số % 2 === 0

Vì vậy, hãy bắt đầu tạo hàm JavaScript của chúng tôi để kiểm tra xem một số có phải là số nguyên tố hay không

function isPrime(num) {
  if (num % 2 === 0) {  return false;
 } return true;}
//isPrime(40) gives us a False answer
//isPrime(101) gives us a True answer

Nhớ rằng 2 LÀ số nguyên tố

Tuy nhiên, hàm trên cũng sẽ cho biết 2 không phải là số nguyên tố, vì vậy chúng ta sẽ cần viết lại hàm của mình. Chúng tôi cũng có thể quan tâm đến bất kỳ số nguyên nào khác không phải là số nguyên như 0 và số âm

function isPrime(num) {
 if (num === 2) return true;
 if (num <= 1) return false; if (num % 2 === 0) {
  return false;
   }
 return true;
}//isPrime(0.5) gives us a False answer
//isPrime(2) gives us a True answer
//isPrime(577) gives us a True answer

Từ khóa 'return' báo hiệu sự thoát khỏi chức năng khi nó gặp một câu lệnh đúng. Nếu số là 2, chức năng dừng chạy ở dòng thứ hai

Bạn có thể tìm thấy một danh sách lớn các số nguyên tố đã biết ở đây để giúp bạn kiểm tra chức năng

Không phải tất cả các số không đồng đều là số nguyên tố

Chức năng này hoạt động tốt để kiểm tra xem một số có chẵn hay không nhưng không thành công với các số không đồng đều như 9 và 27 không phải là số nguyên tố

Chúng ta sẽ phải kiểm tra xem tham số có thể được chia thành các thừa số khác (ngoại trừ 1, chính nó và 2) mà không để lại phần dư hay không. Số 9 chẳng hạn cũng có thể chia hết cho 3

Chúng tôi làm điều này bằng cách sử dụng vòng lặp for trong mỗi lần lặp lại, tham số được chia cho một biến vòng lặp khác. Vòng lặp tiếp tục chạy cho đến khi không còn phần dư hoặc không còn biến vòng lặp nào nữa

function isPrime(num) {
 if (num <= 1) return false;
 if (num === 2) return true;  for (let i= 2; i < num; i++) { //we start with 2 to weed               out the even numbers if (num % i === 0) {
  return false;
   }
  }  return true;
 }//isPrime(9) is False
//isPrime(11) is True
//isPrime(27) is False

Hàm tiếp tục lặp và kiểm tra phần dư. Tại mỗi lần lặp, đối số được chia cho một biến vòng lặp mới và phần còn lại được kiểm tra. Nếu số dư bằng 0 nghĩa là số đó chia hết cho số khác không phải chính nó và không phải là số nguyên tố

lưu ý bên lề. Sự khác biệt giữa một tham số và một đối số là gì?
Tham số là các biến được sử dụng như một phần của định nghĩa hàm. Ví dụ: num trong hàm isPrime(num) là tham số

Đối số là các giá trị được truyền cho hàm khi nó được gọi. Ví dụ
số 9 trong isPrime(9) là đối số

Nếu có phần dư, hàm sẽ lặp lại cho đến khi đạt đến giới hạn tại

 i < num

Khi đến lần lặp cuối cùng và vẫn còn phần dư, đối số là số nguyên tố và hàm dừng lại
Chúng tôi kết thúc với một biến vòng lặp nhỏ hơn một số so với tham số vì chúng tôi không quan tâm đến các yếu tố lớn hơn đối số

Một cuộc biểu tình nhanh chóng

Hãy chứng minh điều này với số nguyên tố 5

function isPrime(num) {
if (num <= 1) return false; 
 //5 is larger than 1, so we continue with the function if (num === 2) return true;
 //5 is not 2, so we continue with the function for (let i= 2; i < num; i++) {
  if (num % i === 0) {
  return false;
   }
 }
 return true;}

vòng lặp đầu tiên
1. i = 2 và 2 < 5, vì vậy chúng tôi tiếp tục với vòng lặp
2. 5 % 2 cho số dư nên chúng ta không thoát khỏi vòng lặp mà tiếp tục với i++

Vòng lặp thứ hai
1. i = 3 và 3 < 5, vì vậy chúng tôi tiếp tục với vòng lặp
2. 5 % 3 cho số dư nên chúng ta không thoát khỏi vòng lặp mà tiếp tục với i++

Vòng lặp thứ ba
1. i = 4 và 4 < 5, và chúng ta đã đi đến cuối vòng lặp vì 5 không < 5
2. 5 % 4 cho số dư. Điều này có nghĩa là số 5 là một số nguyên tố

Sử dụng căn bậc hai với số nguyên tố lớn hơn

Số nguyên tố nhanh chóng leo thang thành số khổng lồ. Điều này có nghĩa là vòng lặp for của chúng ta tiếp tục lặp lại từ biến vòng lặp này sang biến vòng lặp tiếp theo trong nhiều lầ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 của một tham số. Căn bậc hai của một số nguyên là số được nhân với chính nó để tạo ra một tích

Căn bậc hai của 81 là 9 vì 9 x 9 = 81

Thay vì lặp từ 2 đến 80 để kiểm tra xem còn số dư nào hay không, chúng ta chỉ có thể lặp đến và bao gồm cả 9, căn bậc hai của 81
9 % 9 = 0, có nghĩa là 81 không phải là số nguyên tố

Điều này hợp lý vì 9 x 9 là thừa số của 81, nghĩa là nó không tuân theo định nghĩa về số nguyên tố — một số chỉ có thể chia hết cho chính nó và 1

Trong JavaScript, bạn có thể tìm căn bậc hai của một số bằng cách sử dụng Math. Quảng trường. Chúng tôi viết nó như thế này

Math.sqrt(num);

Hãy sử dụng nó trong hàm kiểm tra xem một số có phải là số nguyên tố không

function isPrime(num) {
 if (num <= 1) return false;
 if (num=== 2) return true; let num2 = Math.sqrt(num);//num2 is the square root of num for (let i= 2; i <= num2; i++) { //note that we are working now with the square root  if (num2 % i === 0) {  return false;
   }
 }
  return true; }isPrime(521) //is True
isPrime(9801) //is False
isPrime(13037) //is True

Tại sao số nguyên tố rất hữu ích?

Trong Contact, cuốn sách khoa học viễn tưởng của Carl Sagan, người ngoài hành tinh gửi một chuỗi dài các số nguyên tố làm bằng chứng cho thấy thông điệp của họ là từ một lực lượng sống thông minh. Chúng tôi không (chưa) liên lạc với người ngoài trái đất thông qua các số nguyên tố nhưng sử dụng chúng theo nhiều cách khác nhau ngay tại đây trên hành tinh Trái đất

Ve sầu xuất hiện đồng bộ theo chu kỳ số nguyên tố chính xác. Các chu kỳ không đều có nghĩa là không có động vật ăn thịt nào tiến hóa để sống nhờ những loài côn trùng này. Ngoài ra, thực tế là tất cả chúng đều trồi lên khỏi mặt đất vào thời điểm làm tăng cơ hội sống sót của một cá nhân.

Màn hình sử dụng các số nguyên tố để xác định cường độ màu của pixel. Chúng cũng được sử dụng trong sản xuất công cụ để loại bỏ sự hài hòa. Hai bánh răng chia sẻ nhiều lần sẽ ăn khớp với nhau nhiều lần, dẫn đến kiểu mòn không đều. Bánh răng có số lượng răng nguyên tố trên bánh răng của chúng sẽ tồn tại lâu hơn

Tuy nhiên, các số nguyên tố chủ yếu là trong bảo mật máy tính hiện đại. Tìm số nguyên tố lớn thì không khó nhưng quy các số lớn thành số nguyên tố thì rất khó

Dễ dàng tìm ra 27 là 3 x 3 x 3 nhưng khó hơn nhiều để tìm ra 2.244.354 là 2 x 3 x 7 x 53.437. Và 2.244.354 thậm chí không phải là một con số lớn. Việc tìm các thừa số nguyên tố về mặt kỹ thuật là vấn đề thời gian nhưng vì sẽ mất nhiều thời gian nên chúng tôi nói rằng không thể thực hiện được

Các thuật toán mã hóa hiện đại sử dụng thực tế là chưa có máy tính nào có thể lấy một số siêu lớn và nhanh chóng tìm ra các số nguyên tố nào đã tạo ra nó

Có thể bạn đang mua sắm trực tuyến hoặc gửi tin nhắn được mã hóa qua một ứng dụng trên điện thoại nhưng ở đâu đó, bằng cách nào đó, các số nguyên tố đang giúp bạn giữ bí mật an toàn

Làm cách nào để lấy số nguyên tố trong JavaScript?

Làm cách nào để tìm số nguyên tố từ 1 đến 50 trong JavaScript?

Làm cách nào để tìm số nguyên tố trong mảng JavaScript?