Algorytmy

Liczby Pierwsze

  • 2008-12-18 01:54
  • 7 komentarzy
  • 17995 odsłon
  • 1/6
Liczby Pierwsze jest to liczba, która ma DOKŁADNIE dwa dzielniki, siebie oraz 1.

Pokażę za chwilę, jak napisać prostą funkcję, która będzie sprawdzała czy liczba jest pierwsza.

Jak sprawdzać?



Jednym z najprostszych sposobów jest, sprawdzanie wszystkich liczb od 1 do n, czy podzieli się n przez postęp iteracji i zapisywać do zmiennej typu Integer, gdy ilość podzieleń będzie większe od 2 zwrócić fałsz, a gdy będzie równe 2, zwrócić prawdę.

Inplementacje



C/C++:

bool Pierwsza(int n)
{
 int p=1;
 
 if (n == 1)
  return false;
 
 for (int i=1; i<n; i++)
 {
  if (n%i == 0)
   {
    p++;
    if (p>2)
     return false;
   }    
 } 
 return true;  
}


Pascal:

function Pierwsza(n: LongInt):Boolean;
var
 I,P: LongInt;   // Zmienna iteracyjna, oraz do zliczenia ilosc dzielnikow
begin
 P:=0; // Inicjacja zmiennej
 Pierwsza:= True; // Domyslnie, ustawienie ze liczba jest pierwsza
 
 if n = 1 then       // sprawdzanie wyjatku, czyli liczby 1
 begin
  Pierwsza:=False;
  Exit;
 end;
 
 for I:=1 to N do
  if N mod I = 0 then
   begin
    P:=P+1;      // Dodanie jednego dzielnika
    if P>2 then  // Jezeli ilosc dzielnikow jest wieksza niz 2 to:
    begin
     Pierwsza:= False; // Ustaw rezultat funkcji, na nieprawde (False)
     Break;          // Przerwij iteracje, gdyz nie potrzeba wiecej dzielnikow zliczac
    end;
   end;
end;


PHP:

function pierwsza($n)
{
 if ($n == 1)
 {
  return 0;
  exit;
 }
 
 $p = 1;
 for ($i=1; $i<($n-1); $i++)
 {
  if ($n%$i == 0)
  {
    $p++;
   if ($p > 2)
   {
    return 0;
   }
  }
 }
 return 1;
}

7 komentarzy

elkozirro 2012-06-06 00:11

a do assemblera taki kod jakby wyglądał?? bo akurat bym potrzebował ;)

Coldpeer 2008-12-21 19:28

tak sie zastanawiam co z tym zrobić, usunac? [niski poziom merytoryczny...]

Oleksy_Adam 2008-12-20 22:46

Już na samym wstępie można zmniejszyć liczbę iteracji o 50% bo liczby parzyste to raczej pierwszymi nie będą.

ŁF 2008-12-18 16:50

po co po raz kolejny to samo? :/ żeby jeszcze coś nowego było. weź to usuń i ewentualnie popraw któryś z istniejących artykułów.

przydałoby się stochastyczne sprawdzanie pierwszości.

abc 2008-12-18 00:04

Nawet jeżeli było to można nieco szybciej:

#include  <cmath>
 
bool Pierwsza(int n)
{
 if (n==2) return true;
 if ((n == 1) || !(n%2))
  return false;
 
 for (int i=3; i<ceil(sqrt(n)); i++)
 {
  if (!(n%i))
     return false;
 }
 return true; 
}

Potwoor_ 2008-12-17 22:55

Liczby pierwsze - szybki algorytm
Sito Eratostenesa
Wyszukiwanie liczb pierwszych

i chyba widziałem jeszcze jeden kiedyś
przydało by się zrobić w liczbach pierwszych porządek =]

manfredek 2008-12-17 22:26

Lol. Wolne to jak ...