Liczby Pierwsze

mgx8

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ć?

<font name="Courier New">

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

<font name="Courier New">

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

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

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

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

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.

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; 
}

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 =]

Lol. Wolne to jak ...