Nejčtenější:

Štítky článků:

Archiv:

✕

Načítám ...

Prvočísla v JavaScriptu

Před nějákým časem se moje sestra ve škole učila cosi o JavaScriptu. Mimo jiné dostala taky úkol. Měla vygenerovat zadaný počet prvočísel. Samozřejmě sem jí s úkolem pomohl, ale napsal jsem i nějáké jednoduché funkce, které dělají další psí kusy s prvočísly. Třeba to někomu, kdo se octne ve stejné situaci, někdy pomůže.

Chci zadaný počet prvočísel

Než začneme psát jakýkoliv kód, měli bychom si promyslet, jak přijít na to, že je číslo prvočíslo. Prvočíslo je číslo, které lze dělit jedničkou a sebou samým. Dělíme-li ho jakýmkoliv jiným prvočíslem, nemůžeme dostat nulu jako zbytek po dělení. Naopak pro dělení čísel složených existuje alespoň jedno prvočíslo, které dává zbytek 0. Zároveň platí, že tohle prvočíslo musí být menší nebo rovno druhé odmocnině našeho čísla.

Jak tedy nalezneme třeba první 4 prvočísla? Budeme postupovat postupně od 1. Jednička prvočíslo není. Co 2, to prvočíslo je, s tím nic neuděláme. Co 3, no to je zase prvočíslo, protože tu není žádně číslo menší než jeho druhá odmocnina, které by prvočíslo bylo - stejné jako u 2. Teď číslo 4. Vidíme, že je dělitelné našim prvním prvočíslem 2, které je zároveň druhou odmocninou čtyřky. No a 5 je prvočíslo, protože pět děleno dvěma je dva a půl. Máme první čtyři prvočísla!

Teď známe způsob ověřování a stačí nám vytvořit skript. Naše jednoduchá aplikace by se nejprve měla zeptat na počet prvočísel, který chceme najít. K tomu nám dopomůže funkce prompt(), která zajistí vyskakovací okno, do kterého můžeme zadat jakoukoliv hodnotu. Tuto hodnotu bychom měli převést na číslo - funkce parseInt() a následně bychom ji měli ověřit (přirozené číslo) pomocí regulárního výrazu. Kód může vypadat takhle:

JavaScript

function primeNumber()
{	
   var n = parseInt( prompt(), 0 ), 
      // Vyskočí dialogové okno a zadannou hodnotu
      // převedenou na číslo přiřadí proměnné n.
      reg = /^\d+$/; 
      // Proměnnou reg naplníme regulárním výrazem

    // Zjistíme zda-li n odpovída reg výrazu a není nula 
   if ( !reg.test(n) || n === 0 ) {

      alert("Není přirozené číslo!");
      primeNumber(); // Náš skript se spustí znovu
      return false;

    }     
} 
primeNumber(); // Spustí funkci

A teď k samotnému hledání prvočísel. Procházet všechna čísla nám pomůže cyklus for. Ten bude procházet stále nová čísla o jedna větší do té doby, než získáme zadaný počet prvočísel. V tomto cyklu bude další cyklus for, který bude testovat dělitelnost všemi prvočísly menšími a rovnými než je druhá odmocnina právě prověřovaného čísla. Pokuď narazí na zbytek po dělení 0, přeruší se a číslo zaznamená do pole nazvaného primes, v kterém shromažďujeme prvočísla.

Nakonec můžeme pole prvočísel primes vypsat pomocí dalšího cyklu. Celý skript může vypadat následovně:

JavaScript

function primeNumber(){

  var n = parseInt( prompt(), 0 ),
      reg = /^\d+$/, 
      prime = [];

  if ( !reg.test(n) || n === 0 ) {
    
    alert("Není přirozené číslo!");
    primeNumber();
    return false;
    
  } 
  
  for ( var i = 2; prime.length <= n-1; i++ ) {
  
    var nonprime = false;
    for (var j = 0; j < prime.length; j++ ) {
      
      if ( prime[j] > Math.sqrt(i) ) break;
      if ( i % prime[j] === 0 ) {
        nonprime = true;
        break;
      }
      
    }
    if ( !nonprime ) prime.push(i);
    
  } 
  
  for ( var k = 0; k < prime.length; k++ ) {
  
    if( k === prime.length-1 ) document.write(prime[k]);
    else document.write(prime[k]+", ");
  
  }
} 

primeNumber();

No a to je všechno. Klepnutím sem spustíte skript výše.

Jak na prvočísla do čísla

Pokuď bychom chtěli najít všechna prvočísla menší než zadané číslo, využili bychom jinou, kratší a rychlejší metodu - Erastothenovo síto. Budeme procházet každé číslo a pokuď přijde na to, že je prvočíslo, všechny jeho násobky menší než zadané n přidáme do pole other. Pro další čísla se budeme koukat, jestli už náhodou číslo v poli není.

JavaScript

function primeNumber(){

  var n = parseInt( prompt(), 0 ),
      reg = /^\d+$/, 
      prime = [],
      other = [];

  if ( !reg.test(n) || n === 0 ) {
    
    alert("Není přirozené číslo!");
    primeNumber();
    return false;
    
  } 
  
  for ( var i = 2; i <= n; i++ ) {
    
    if ( !other[i] ){
      
      prime.push(i);
      for ( var j = i; j <= n; j += i ) other[j] = true;
         
    } 
    
  } 
  
  for ( var k = 0; k < prime.length; k++ ) {
  
    document.write(prime[k]+",");
  
  }
} 

primeNumber();

napsal Tomáš Nekvinda

Komentáře k článku

Lucie Nekvindová:

Tak dík, bratře ;-)!4. Duben 2015, 18:36 reagovat

---

Přidat nový komentář

nebo po přihlášení přes účet sociálních síťí

odhlásit z Facebooku odhlásit z Google+