Wyjaśnij mi ktoś krok po kroku jak działa wyznaczanie liczb pierwszych?

Question

Mimo, że wyobraźnię mam bogatą nie potrafię pojąć jak odbywa się wyznaczanie liczb pierwszych. Czy mógłby mi to ktoś wytłumaczyć? Tutaj przykładowy kod z jakiejś strony:

bool czy_pierwsza(int n)
{
  if(n<2)
    return false; //gdy liczba jest mniejsza niż 2 to nie jest pierwszą
 
  for(int i=2;i*i<=n;i++)
    if(n%i==0)
      return false; //gdy znajdziemy dzielnik, to dana liczba nie jest pierwsza
  return true;
}

 

Comments

Kod który przedstawiłeś zawiera błąd. Postaraj się go odnaleźć a jeśli nie dasz rady, to powiem Ci gdzie jest :) Pozdrawiam.

Answer 1

Po prostu sprawdzasz, czy tę liczbę można podzielić przez inną liczbę. Jeśli liczba jest niepodzielna, to jest pierwsza. Zaczynasz podstawiając za dzielnik 2, a kończysz gdy dojdziesz do pierwiastka danej liczby, bo dalej nie trzeba już sprawdzać.

Answer 2

Jest też sito Eratostenesa. Możesz sobie o nim doczytać.

Comments

Jest jeszcze inna metoda sito Małgorzaty pod linkiem: https://1drv.ms/b/s!AsqwpKK-51whhhzzvgOxdib8Y_rW

lub

algorytm opisany pod linkiem: https://1drv.ms/b/s!AsqwpKK-51whhyrXq3rEvKSwC62Q

Ilość interacji algorytmu pierwiastek z liczby dzielony przez trzy.

Pod linkiem :https://1drv.ms/b/s!AsqwpKK-51whhyxst9k9X9-1unaI zamieściłem algorytm Iteracje Kamila. Pokazuje jak iteracyjnie obliczać resztę z liczby. W efekcie daje takie same reszty z dzielenia co algorytm Krystyny i operuje na mniejszych liczbach. W obu algorytmach można zastosować przetwarzanie rozproszone. Z algorytmów widać, że rozkład  liczb złożonych wokół danej liczby nie jest losowy. Stąd też wynika, że i odległości liczb pierwszych też nie są przypadkowe.

---

Jako ciekawostkę przedstawiam Fraktal Rafała, który można opisać wzorem:
f(y)= n + x * (-1)^{n} + (3*x + 0.5 - 0.5 * (-1)^{x}) * (n + 0.5 - 0.5 * (-1)^{n})
gdzie n > 0 i x >0 oraz x,n należy do liczb naturalnych. Liczba x określa kolejne wystąpienie liczby "złożonej" dla n. Dodatkowo zachodzi zależność jezeli:
x parzyste, n parzyste to f(y) parzyste
x parzyste, n nieparzyste to f(y) nieparzyste
x nieparzyste, n parzyste to f(y) nieparzyste
x nieparzyste, n nieparzyste to f(y) parzyste

Związek liczb złożonych z fraktalem Rafała jest następujący:
f(z)= 3 * f(y) + 1.5 - 0.5 *(-1)^{x+n}
gdzie f(y) funkcja generująca liczby tworzące fraktal Rafał dla wartości x i n.

Jeżeli dla wzoru f(y) wprowadzimy ograniczenie x >= n oraz f(y) <= Ym to otrzymamy sito Małgorzaty w przedziale liczb naturalnych (1,Ym).