[C]Liczby pierwsze

Dla specjalistów Programowanie
#1

Witam,

Mam problem z kolejnym zadaniem.

#include 

#include 

#define MAX 100000



main()

{

int i;

int x;

int range;

int dokad;

int tablica[MAX];



printf("Podaj zakres\n");

scanf("%d",&range);



dokad=floor(sqrt(range));

    for (i=1; i<=range; i++) tablica[i]=1;

    for (i=2; i<=dokad; i++){

        if (tablica[i] != 0){

            x = i+i;

            while (x<=range){

                tablica[x] = 0;

                x+=i;

            }

        }

    }

printf("Liczby pierwsze z zakresu od 1 do %d\n\n",range);

    for(i=2; i<=range; i++)

        if(tablica[i]!=0)

            printf("%6.d ",i);


printf("\nf(n)=%f\n",range/log(range));


}

Nie wiem jednak jak sprawić by dodatkowo wyliczał ile jest tych liczb pierwszych w przedziale.

Nie wiem też jak sprawić by sprawdzał liczby pierwsze dla zakresu liczb z 1000000.

Przy 100000 program się zawiesza i wyświetla się błąd:

#2

  1. Tablica jest indeksowana wartościami 0 … MAX-1. Ty natomiast w warunkach pętli masz <=, czyli teoretycznie może wyjść poza tablicę. Jeśli sito ma obejmować liczby od 0 do N, tablica powinna mieć N+1 elementów.

  2. Dla dużych tablic użyj raczej dynamicznej alokacji - malloc, free.

  3. Najpierw wszystkie liczby oznaczasz jako pierwsze, a potem wykreślasz złożone. Czyli możesz użyć licznika, zainicjować go na szerokość przedziału, a potem w miejscu gdzie oznaczasz liczby jako złożone, dekrementować ten licznik.

#3

Może mnie ktoś uświadomić po co tutaj w ogóle jakakolwiek tablica?

Na moje oko wystarczy jedna funkcja sprawdzająca czy liczba jest pierwsza, oraz druga funkcja przyjmująca w argumentach zakres liczb do sprawdzenia i licząca ilość pierwszych przy użyciu pierwszej funkcji.

#4

somekind - a jak chciałbyś sprawdzić, czy liczba jest pierwsza? Nie piszę w C, jednak zrobiłbym tak:

  • tworzysz tablicę, o rozmiarze n (zapełnioną wartościami 0)

  • w pętli, zaczynając od 2 wykreślasz kolejne wielokrotności (zmieniając wartośc na 1)

  • na koniec wyświetlasz te indeksy, dla których wartość jest 0 (dodając 1).

Pozdrawiam

#5

ptasior , sprawdziłbym jej parzystość, a następnie podzielność przez liczby nieparzyste począwszy od 3 do pierwiastka z tej liczby. Żadna tablica tu nie jest do niczego potrzebna.

#6

I myślisz że byłaby to wydajna metoda? Po jaką cholerę używać tak naiwnej metody, skoro można skorzystać z sita eratostenesa i na koniec zliczyć tylko 0 występujące w tablicy?

#7

Wbrew pozorom test naiwny po przedziale nie musi być bardzo wolny. Dla argumentów do miliona, bo chyba o takim ograniczeniu wspominał autor wątku, powinno i tak być wystarczająco szybko. Z ciekawości sprawdziłem u siebie i różnica to mniej więcej 0.2s dla naiwnego testu i 0.02s dla sita.

#8

Ciekawe, ciekawe. Czyli przy teście naiwnym wyliczyło w 0.2s a przy sicie w 0.02s?

#9

Spytałeś, jak chcę sprawdzić nie używając tablicy, więc Ci odpowiedziałem. Tablica jest całkowicie zbędna w tym procesie i to jest fakt. Można skorzystać z sita, w zakresie do miliona będzie działało nawet nieźle, ale z miliardem już chyba będzie problem. A jak jest z jego wydajnością przy testowaniu pojedynczych liczb?

– Dodane 09.01.2012 (Pn) 0:39 –

Niektórzy za to potrafią go bardzo wolno zaimplementować.

Mi również wychodzi rząd wielkości różnicy.

#10

Zależnie ile ma pamięci ale do miliona (raczej), można sobie pozwolić na stablicowanie i podanie odpowiedzi w czasie O(1).

Ewentualnie stablicować nie wszystkie liczby, tylko liczby pierwsze i podać odpwiedź w czasie O(lgn) też byłoby całkiem nieźle, liczb pierwszych w tym zakresie nie ma b. dużo.