Błąd w algorytmie szukającym liczb pierwszych

Błąd w algorytmie szukającym liczb pierwszych
J1
  • Rejestracja:ponad 8 lat
  • Ostatnio:7 miesięcy
  • Postów:6
0

Witam!
piszę program w którym potrzebuje znać liczby pierwsze w przedziale <0, x>. Funkcja ma działać w ten sposób że w tablicy[x-1] są wartości <2, x>. Elementom tablicy które nie maja liczb pierwszych jest przypisywana wartość 1. Jednak gdy program dochodzi do tej funkcji i przestaje działać. Oto ta funkcja:

Kopiuj
//... program...
int* pierwsze = new int[x - 1];

liczby_pierwsze(pierwsze, x);
//..............

void liczby_pierwsze(int tab[], int n)
{
    for (int i = 0; i < n; i++)
        tab[i] = i + 2;

    for (int i = 0, x = 2; x < sqrt(n); i++, x++) {
        if (tab[i] != 1) {
            for (int k = i + 1; i <= n; k++) {
                if (tab[k] % tab[i] == 0)
                    tab[k] = 1;
            }
        }
    }
}

Możecie mi pomoc znaleźć błąd?

Z góry dzięki :)

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
3

Już w pierwszej pętli wychodzisz poza zakres tablicy.
W ramach testu przyjmij, że x = 10 i leć sobie w głowie po kolei każdą instrukcję kodu.


J1
  • Rejestracja:ponad 8 lat
  • Ostatnio:7 miesięcy
  • Postów:6
0

Możesz powiedzieć dokładnie gdzie? Czy to chodzi o

Kopiuj
for (int i = 0, x = 2; x < sqrt(n); i++, x++)

bo ja nie mogę znaleźć błędu o którym mówisz.

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
3

Czy to chodzi o (...)
No akurat liczenie do dwóch to powinieneś mieć opanowane w małym paluszku. Napisałem wyraźnie, iż chodzi o pierwszą pętlę, a Ty mnie pytasz czy aby nie o drugą.

Kopiuj
// Zakładamy, że x = 10

// Alokujesz tablicę o rozmiarze 9, mającą indeksy: 0, 1, 2, ..., 8.
int* pierwsze = new int[x - 1];

liczby_pierwsze(pierwsze, x);

void liczby_pierwsze(int tab[], int n)
{
	// Po czym po tablicy iterujesz kolejno: 0, 1, 2, ..., 8, 9
    for (int i = 0; i < n; i++)
		tab[i] = i + 2;

Jeśli nadal nie widzisz błędu, uruchom debugger i śledź dokładnie wartość każdej zmiennej, mając w pamięci rozmiar Twojej tablicy.


edytowany 1x, ostatnio: Patryk27
J1
  • Rejestracja:ponad 8 lat
  • Ostatnio:7 miesięcy
  • Postów:6
0

Wielkie dzięki za pomoc :) Błędem, który wysypywał program było

Kopiuj
for (int k = i + 1; i <= n; k++) 

zamiast

Kopiuj
for (int k = i + 1; k <= n; k++) 

Ale dzięki za uwagę z przekroczeniem zakresu, nie zauważyłem jakoś tego po prostu :)

edytowany 1x, ostatnio: Jadw1
Shalom
  • Rejestracja:około 21 lat
  • Ostatnio:około 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
1

Ale przecież cały czas masz tam wyłażenie poza tablicę. Skoro zrobiłeś tablicę na x-1 elementów, jako rozmiar mimo to przesyłasz do funkcji x a potem jeszcze w pętli robisz indeks <=x czyli w efekcie wyłazisz o 2 elementy za tablicę, bo ostatni indeks tablicy o x-1 elementach to x-2


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.