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++: ```cpp bool Pierwsza(int n) { int p=1; if (n == 1) return false; for (int i=1; i<n; i++)="i++)" {="{" if="if" (n%i="=" 0)="0)" p++;="p++;" (p="(p">2) return false; } } return true; } ``` Pascal: ```delphi 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: ```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; 
}

http://4programmers.net/Delphi/Gotowce/Liczbypierwsze-_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 ...