Program JavaScript untuk mengira nombor perdana dalam julat

Nombor perdana ialah nombor yang mempunyai tepat dua pembahagi sempurna. Kita akan melihat dua cara untuk mencari bilangan nombor perdana dalam julat tertentu. Yang pertama ialah menggunakan kaedah kekerasan, yang mempunyai kerumitan masa yang agak tinggi. Kami kemudiannya akan menambah baik kaedah ini dan menggunakan algoritma Sieve of Eratosthenes untuk mempunyai kerumitan masa yang lebih baik. Dalam artikel ini, kita akan menemui jumlah bilangan nombor perdana dalam julat tertentu menggunakan bahasa pengaturcaraan JavaScript.

Undang-undang Keganasan

Pertama, dalam kaedah ini, kita akan belajar bagaimana untuk mencari sama ada nombor itu perdana atau tidak, kita boleh mencarinya dengan dua cara. Satu kaedah mempunyai kerumitan masa O(N) dan kaedah lain mempunyai kerumitan masa O(sqrt(N)).

Kaedah langsung untuk menentukan sama ada nombor adalah perdana

Contoh

Pertama, kita akan melakukan gelung untuk sehingga kita mendapat nombor, dan mengira nombor yang boleh membahagi nombor Jika nombor yang boleh membahagi nombor itu tidak sama dengan 2, maka nombor itu bukan nombor perdana, sebaliknya nombor itu. nombor ialah nombor perdana. Mari lihat kod -

function isPrime(number){
   var count = 0;
   for(var i = 1;i<=number;i++)    {
      if(number%i == 0){
         count = count + 1;
      }
   }
   if(count == 2){
      return true;
   }
   else{
      return false;
   }
}

// checking if 13 and 14 are prime numbers or not 
if(isPrime(13)){
   console.log("13 is the Prime number");
}
else{    
   console.log("13 is not a Prime number")
}

if(isPrime(14)){
   console.log("14 is the Prime number");
}
else{
   console.log("14 is not a Prime number")
}

Dalam kod di atas, kita merentasi dari 1 ke nombor, cari nombor dalam julat nombor yang boleh membahagi nombor yang diberikan, dan dapatkan bilangan nombor yang boleh membahagikan nombor yang diberikan, dan mencetak keputusan berdasarkan ini.

Kerumitan masa kod di atas ialah O(N), menyemak sama ada setiap nombor adalah prima akan dikenakan kos O(N*N), yang bermaksud ini bukan cara yang baik untuk menyemak.

Kaedah matematik

Kita tahu bahawa apabila satu nombor membahagikan nombor lain sepenuhnya, hasil bahagi juga adalah integer sempurna, iaitu jika nombor p boleh dibahagikan dengan nombor q, hasil bahagi ialah r, iaitu q * r = p. r juga membahagikan nombor p dengan hasil q. Jadi ini bermakna pembahagi yang sempurna sentiasa datang secara berpasangan.

Contoh

Melalui perbincangan di atas, kita boleh membuat kesimpulan bahawa jika kita hanya menyemak pembahagian kepada punca kuasa dua N, maka ia akan memberikan hasil yang sama dalam masa yang sangat singkat. Mari lihat kod kaedah di atas -

function isPrime(number){
   if(number == 1) return false
   var count = 0;
   for(var i = 1;i*i<=number;i++){
      if(number%i == 0){
         count = count + 2;
      }
   }
   if(count == 2){
      return true;
   }
   else{
      return false;
   }
}
// checking if 67 and 99 are prime numbers or not 
if(isPrime(67)){
   console.log("67 is the Prime number");
}
else{
   console.log("67 is not a Prime number")
}
if(isPrime(99)){
   console.log("99 is the Prime number");
}
else{
   console.log("99 is not a Prime number")
}

Dalam kod di atas, kami baru sahaja menukar kod sebelumnya dengan menukar skop gelung for, kerana sekarang ia hanya akan menyemak punca kuasa dua pertama unsur N, dan kami telah meningkatkan kiraan sebanyak 2.

Kerumitan masa kod di atas ialah O(sqrt(N)), yang lebih baik, bermakna kita boleh menggunakan kaedah ini untuk mencari bilangan nombor perdana yang wujud dalam julat tertentu.

Bilangan nombor perdana dalam julat dari L hingga R

Contoh

Kami akan melaksanakan kod yang diberikan sebelum ini dalam julat dan mengira bilangan nombor perdana dalam julat tertentu. Mari laksanakan kod -

function isPrime(number){
   if(number == 1) return false
   var count = 0;
   for(var i = 1;i*i<=number;i++)    {
      if(number%i == 0){
         count = count + 2;
      }
   }
   if(count == 2){
      return true;
   }
   else{
      return false;
   }
}
var L = 10
var R = 5000
var count = 0
for(var i = L; i <= R; i++){
   if(isPrime(i)){
      count = count + 1;
   }
}
console.log(" The number of Prime Numbers in the given Range is: " + count);

Dalam kod di atas, kami mengulangi julat dari L hingga R menggunakan gelung for, dan pada setiap lelaran, kami menyemak sama ada nombor semasa ialah perdana. Jika nombor itu adalah perdana, maka kami menambah kiraan dan akhirnya mencetak nilai.

Kerumitan masa kod di atas ialah O(N*N), dengan N ialah bilangan elemen dalam Julat.

Penyaringan algoritma Eratosthenes

Contoh

Algoritma Sieve of Eratosthenes berfungsi dengan sangat cekap dan boleh mencari bilangan nombor perdana dalam julat tertentu dalam masa O(Nlog(log(N))) Berbanding dengan algoritma lain, ia sangat pantas. Penapis mengambil ruang O(N), tetapi itu tidak penting kerana masanya sangat cekap. Mari lihat kod dan kemudian kita akan beralih kepada penjelasan kod -

var L = 10
var R = 5000
var arr = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,1);
arr[0] = 0
arr[1] = 0

for(var i = 2;i<=R;i++){
   if(arr[i] == 0){
      continue;
   }
   for(var j = 2; i*j <= R; j++){
      arr[i*j] = 0;
   }
}

var pre = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,0);
for(var i = 1; i<= R;i++){
   pre[i] = pre[i-1] + arr[i];
}
answer = pre[R]-pre[L-1]
console.log("The number of Prime Numbers in the given Range is: " + answer);

Dalam kod di atas, kita melihat pelaksanaan Sieve of Eratosthenes. Mula-mula kami mencipta tatasusunan yang mengandungi saiz R dan selepas itu kami mengulangi melalui tatasusunan menggunakan gelung for dan untuk setiap lelaran jika nombor semasa bukan 1 ia bermakna ia bukan prima sebaliknya ia prima dan kami mempunyai Semua nombor kurang daripada R yang gandaan perdana semasa dikeluarkan. Kami kemudiannya mencipta tatasusunan awalan yang akan menyimpan kiraan perdana daripada 0 hingga indeks semasa dan boleh memberikan jawapan kepada setiap pertanyaan dalam julat 0 hingga R dalam masa tetap.

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N*log(log(N))), yang jauh lebih baik berbanding dengan O(N*N) dan O(N*(sqrt(N))). Berbanding dengan kod sebelumnya, kod di atas mempunyai kerumitan ruang yang lebih tinggi iaitu O(N).

Kesimpulan

Dalam tutorial ini, kami mempelajari cara mencari bilangan nombor perdana dalam julat tertentu menggunakan bahasa pengaturcaraan JavaScript. Nombor perdana ialah nombor yang mempunyai tepat dua pembahagi sempurna. 1 bukan nombor perdana kerana ia hanya mempunyai satu pembahagi sempurna. Kami telah melihat tiga kaedah dengan kerumitan masa O(N*N), O(N*sqrt(N)) dan O(N*log(N))). Di samping itu, kerumitan ruang bagi dua kaedah pertama ialah O(1), dan kerumitan ruang bagi kaedah Ayak Eratosthenes ialah O(N).

Atas ialah kandungan terperinci Program JavaScript untuk mengira nombor perdana dalam julat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!