Sito Eratostenesa

0

Czesc, Mam mały problem z programem a mianowicie nie działa dla zakresu większego niż 3856 i nie wiem jaki jest tego powód. Konsultowałem już z kilkoma osobami jednak nikt nie był mi w stanie pomóc.

#include <stdio.h>
#include <stdlib.h>

//Generator liczb pierwszych do 535 liczb.
//Maksymalna deklaracja tablicy 124 999 999;
//Dziala do zakresu 3856 - powyzej sie zaawiesza.
//Wyswietlanie wszystkich liczb spowalnia
//Jednakowo dziala dla CodeBlock i Dev

unsigned long int tab[8048];
unsigned long int pierwsza[8048] = { 2, 3 }; //Poczštkowy zbior dwoch liczb

int main()
{
    //deklaracja zmiennych
    unsigned long int a, b, c, m, i, p, n;

    //podanie zakresu do jakiego ma szukac
    printf("Podaj wartosc zakresu dla wyznaczenia liczb :");
    scanf("%lu", &m);

    //Wypelnienie tablicy liczbami z zakresu
    for (i = 0; i <= m; i++) {
        tab[i] = i;
    }

    //Wartosci poczatkowe
    a = 1; //zakres
    b = 2; //Ilosc liczb pierwszych
    c = 1;

    while (c <= m) {
        //wyznaczenie zakresu na podstawie zaleznosci
        a = pierwsza[b - 1] * 2;
        //zerowanie w tablicy wartosci nie bedacych pierwszymi
        //dla danego zakresu
        for (i = 0; i < b; i++) {
            n = 2;
            while (pierwsza[i] * n <= a) {
                p = pierwsza[i] * n;
                tab[p] = 0;
                n++;
            }
        }
        //policzenie liczb pierwszych
        b = 0;
        for (i = 2; i <= a; i++) {
            if (tab[i] != 0) {
                b++;
            }
        }
        //Wpisanie do tablicy nowych liczb pierwszych
        n = 0;
        for (i = 2; i <= a; i++) {
            if (tab[i] != 0) {
                pierwsza[n] = tab[i];
                n++;
            }
        }
        //c=pierwsza[b-1]; >> tak powinno być
        c = pierwsza[b - 1] + 4; //działa tylko dla 4 i więcej
    }

    printf("Liczby to:\n");
    //wyswietlenie liczb
    for (i = 0; i < b; i++) {
        printf("%lu\n", pierwsza[i]);
    }
    printf("\nNajwieksza liczba pierwsza %lu\n", pierwsza[b - 1]);
    printf("\nLiczb pierwszych jest:%lu\n", b);
    system("PAUSE");
    return 0;
}

0

Spróbuj wsadzić kod w odpowiednie znaczniki.

5
  1. Popraw formatowanie kodu - w obecnej wersji nie da się go czytać (c++ code formatter w Google).
  2. Popraw komentarze - powinny one dopełniać kod, a nie tłumaczyć to, co na pierwszy rzut oka i tak widać; np. komentarz deklaracja zmiennych nie ma sensu (no bo przecież widzę, że to deklaracja zmiennych), a za to przydałby się komentarz tłumaczący skąd wzięła się liczba 8048 (ponieważ jej wartość nie jest oczywista).
  3. Co to znaczy nie działa? Pokazują Ci się nieprawidłowe wyniki (jakie?), komputer Ci wybuchł etc.
3

Kontynuując porady Patryka27:

    a = 1; //zakres
    b = 2; //Ilosc liczb pierwszych

Nie myślałeś czasem o nazywaniu zmiennych tak, żeby komentarze dotyczące ich znaczenia nie były potrzebne?

0

Ad.1 W przyszłych postach postaram się pisać z dobrym formatowaniem.
Ad2. Przepraszam za opisy ale starałem sie opisać sobie to jak najbardziej szczegółowo, by później nie zastanawiać się nad odpowiedzią. Liczba to zakres tablicy i równie dobrze można podać inne( chodzi o zakresy dla jakich mozna szukać liczb pierwszych).
Ad3, Do zakresu 3856 szuka normalnie liczb pierwszych dla danych zakresów, jednak powyżej tej wartości zawiesza sie i przestaje działać. Właśnie tutaj jest problem bo można używać go tylko do generowania 535 liczb a później z niewiadomych powodów nie działa.

Zmienne mógłbym inaczej nazywać, jednak mam jeszcze taki zły nawyk.

0

Liczba to zakres tablicy i równie dobrze można podać inne( chodzi o zakresy dla jakich mozna szukać liczb pierwszych).

Wiem, że ta liczba determinuje rozmiar tablicy; moje pytanie brzmiało: dlaczego wybrałeś akurat 8048?

0

Początkowo ustawiłem 2048 a później zmieniłem tylko pierwszą liczbę na większą. Nie było w tym jakiegoś większego sensu.

2

Nie uważasz, że Twoja implementacja jest... przesadnie skomplikowana?

Podstawową wersję Sita Eratostenesa można opisać paroma zdaniami oraz wytłumaczyć uczniowi w podstawówce, podczas gdy Twój kod w "najgłębszym miejscu" (linia 40) składa się z trzech zagnieżdżonych pętli, wielu podejrzanych odejmowań i mnożeń.

Przykładowo nie mam pojęcia co robi c = pierwsza[b - 1] + 4; czy też za co odpowiada sekcja //policzenie liczb pierwszych (która zdaje się wcale nie liczyć żadnych liczb pierwszych).

Na Twoim miejscu spróbowałbym wyrzucić cały ten program i napisać od zera - tak, aby najgłębszy fragment kodu składał się z maksymalnie dwóch pętli for - nie licząc instrukcji warunkowych, naprawdę nie potrzeba tutaj nic więcej.

Btw, nie potrzebujesz też dwóch tablic.

1


temat trzynasty

4 minuty, fajnie wytłumaczone. Później zakoduj po prostu te dwie pętle operujące na tablicy i gotowe.

Nie zaczynaj od kodowania, zacznij od zrozumienia tematu, zrób przykład na kartce, wyłap jak to działa, dopiero koduj w konkretnym języku.

0

Sito, np., znajduje się tutaj:
https://www.geeksforgeeks.org/sieve-of-eratosthenes/

1 użytkowników online, w tym zalogowanych: 0, gości: 1