Algorytmy

Wyszukiwanie liczb pierwszych

TeWuX

Wyszukiwanie liczb pierwszych

Do znajdowania liczb pierwszych bardzo szybkim algorytmem jest Sito Eratostenesa. Jednak ma ono jedną wadę. Musimy zadaklaorwać bardzo dużo tablicę (o długości przeszukiwaniego zakresu).

Jest również naiwny algorytm, który w ogóle nie korzysta z tablicy. Który w podwójnej pętli sprawdza wszystkie liczby z zakresu od 2 do N czy są podzelnie przez liczby od 2 do ?N. Niestety ten algorytm jest dużo wolniejszy od Sita Eratostenesa.

Postanowiłem połączyć oba sposoby (na pewno już ktoś kiedyś wpadł na ten pomysł ;-)
Mój algorytm będzie potrzebował tablicę o długości tylko ?N (gdzie N to górny zakres wyszukiwania).
Do tablicy będę zapisywał liczby pierwsze, ale tylko te które są mniejsze od ?N, ponieważ tylko takich będziemy potrzebowali, aby sprawdzić wszystkie liczby z zakresu od 2 do N.
Teraz podobnie do naiwnego alorytmu będzie sprawdzał co drugą liczbę zaczynając od 3.
Jednak do sprawdzenia czy liczba jest pierwsza skorzystam z tabicy liczb pierwszych, którą uaktualniam podczas wykonywania algorytmu.

Nie wiem czy to dobrze opisałem, więc przykład implementacji algorytmu w C:

#include <stdio.h>
#include <math.h>

unsigned long i,j,n, p,pierw, ilosc;

int main(void)
{
  printf("Podaj gorny zakres: ");
  scanf("%d", &n);

  pierw = sqrt(n)+1;
  unsigned long T[pierw];
  unsigned long THigh = 0;
  T[0] = 2;
  
  if (n>=2) printf("2\t"); 
    
  for (i=3; i<=n; i+=2)
  {
      p = sqrt(i)+1;
      for (j=1; (j<=THigh) && ((i%T[j])!=0) && (T[j]<=p); j++);
      if ((j>THigh)||(T[j]>=p))
      { 
         ilosc++;
         printf("%d\t", i);
         if (i <= pierw) T[++THigh]=i;
      }
  }
  
  printf("\nIlosc liczb pierwszych : %d\n\n", ilosc);  
  
  system("PAUSE");	
  return 0;
}

<font size="1">Komentarz do implementacji: Program będzie wypisywał pokolei liczby pierwsze na ekran, co spowalnia nieco cały program. Przy zapisie do pliku program działa szybciej.</span>

Algorytm jest dużo szybszy od naiwnego algorytmu i moim zdaniem nie wiele odbiega od Sita. Jednak w porównaniu do Sita możemy sprawdzić większy zakres liczb.

</p>

Zobacz też

*[[Algorytmy/Sito Eratostenesa]]
Algorytmy

8 komentarzy

TeWuX

po sesji poprawie i spróbuje zastosować, to o czym pisales.

Xitami

Przykład działania programu:
Podaj gorny zakres: 10
2 3 5 7
Ilosc liczb pierwszych : 3

Aby kontynuować, naciśnij dowolny klawisz . . .

 
Wyświetlasz X liczb, a później piszesz że ?Ilość liczb pierwszych to X-1?.
2 jest uważana teraz za liczbę pierwszą, choć nie zawsze tak było. Czyli w programie należałoby poprawić:
printf("\nIlosc liczb pierwszych : %d\n\n", ilosc + 1);

Można zaoszczędzić 1/3 czasu dzięki małej sztuczce. 
Pomińmy nie tylko wielokrotności 2 (i+=2 w pętli po ?i?) ale i wielokrotności 3.
05 07 09 11 13 15 17 19 21 23 25 ...
XX XX -- XX XX -- XX XX -- XX XX ... 
W pętli po ?i? nie dodawajmy 2, lecz zmienną np. ?krok? która przyjmuje na przemian wartości 2 albo 4, krok= 6 ? krok.
M6

tak a propo... www.spoj.pl -> zadanie Prime generator. stosuje sie powyższy algorytm i po zadaniu:)

TeWuX

w wielu artykułach na 4p spotkałem sie z nagłówkiem nad artykułem :D ... to chyba nic dziwnego jak ponad tekstem jest duży tytuł. ;)

Marooned

Fakt, nie czytałem.. [wstyd]
Niemniej jednak, link jest przydatny jako info do materiałów powiązanych :)

Coldpeer, mi się to podoba, wytłuszczony tytuł w treści - a nie jako kawałek adresu czy co tam..

Coldpeer

Mnie tylko dziwi zawsze jak tytuł jest na górze i w tytule (każdy wie co czyta), a tu nagłówek

z tytułem na początku tekstu... :)</p>

TeWuX

Sorry, ale chyba nie czytałeś mojego artykułu.
On przedstawia metode alternatywną do Sita, która nie potrzebuje aż takiej dużej tablicy.

Marooned

Tutaj jest świetny i zwięzły artykuł o tym
http://4programmers.net/Algorytmy/Sito_Eratostenesa