Algorytmy

Wyszukiwanie liczb pierwszych

  • 2006-05-12 12:57
  • 8 komentarzy
  • 5868 odsłon
  • Oceń ten tekst jako pierwszy

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

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.

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.



Zobacz też


8 komentarzy

TeWuX 2006-06-30 18:48

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

Xitami 2006-06-19 15:35

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.

master66 2006-05-22 00:21

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

TeWuX 2006-05-11 20:44

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 2006-05-11 18:55

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 2006-05-11 17:45

Mnie tylko dziwi zawsze jak tytuł jest na górze i w tytule (każdy wie co czyta), a tu nagłówek <h1> z tytułem na początku tekstu... :)

TeWuX 2006-05-11 17:22

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 2006-05-11 17:15

Tutaj jest świetny i zwięzły artykuł o tym
Sito Eratostenesa