Proszę o pomoc w napisaniu kodu, który szuka liczby pierwszej. Ponadto, jaką funkcją mogę wydobyć czas systemowy. Potrzebuję wyświetlić czas początku szukania liczby lierwszej z danego przedziału i czas zakończenia.
Dzięki za pomoc
0
0
ja cie tylko naprowadze - do szukania liczby pierwszej wykozystaj sito erastotenesa - jest bardzo prosty w implementacji choc niezbyt szybki...
czas pobiezesz funkcja gettime() posiadajaca 4 parametry godzian, minuta sekunda i sekunda etna - o ile sie nie myle to ta funkcja jest w pliku naglowkowym dos.h. Parametry te sa typu time_t, czyli implementacja:
time_t g,m,s,sek;
gettime(g,m,s,sek);
ps. jezeli sie gdzies pomylilem to poprawcie bo pisze z glowy a adwno nie wykorzystywalem funkcji czasowych...
0
Sito Eratostenesa rzeczywiście jest dobrym sposobem na znajdywanie liczb pierwszych ale , wg mnie jedynym sposobem jest użycie tablicy jednowymiarowaj to tego algorytmu ( numer indeksu+3 może być daną liczbą , a element tablicy o tym indeksie , może przybierać 0 - gdy nie jest zakreślony ani skreślony , 1- zakreślony,czyli l.pierwsza , 2-skreślony ) . Ja tak to widze . Tylko , że jest problem , gdyż tablice nie mogą przybierać zbyt dużych rozmiarów , a to ogranicza ilość liczb do sprawdzenia czy są pierwsze . Może miałeś na myśli inny sposób implementacji tego algorytmu anubisie , bo mi nie przychodzi do głowy inny pomysł ... [glowa]
Ale można to też rozwiązać ten problem w inny sposób . jest takie twierdzenie , które mówi że wystarczy sprawdzić czy dana liczba nie jest podzielna przez wszystkie liczby pierwsze mniejsze od pierwiastka z niej samej . Jeśli taka l.pierwsza
0
aby ominac problem trudnej do przeiwdzenia w rozmiarze tablicy, proponuje uzyc dwoch kolejek - program taki jest dostepny w kodach zrodlowych, nietstety w Pascalu - jednak jnie sadze aby byl problem z przerobieniem go na C.
A tak w skrocie:
Mamy dwie kolejki p i q. W kolejce p znajduja sie liczby z zakresu od 2 do.... Deklarujemy kolejke pomocnicza w. W drugim kroku sprawdzamy czy kolejna liczba z p jest podzielna przez ostatni wyraz znajdujacy sie w q, jezeli tak to przenoszona jest do kolejki w, jezeli nie to usuwana. Krok ten powtza sie do momentu oproznienia kolejki p. W trzecim kroku przenosimy zawartosc kolejki w do kolejki p - i zaczynamy proces od nowa.
Co nam to zagwarantuje??
- nie problemu z rozmiarami tablic - jedynym ograniczeniem jest ilosc pamieci
- wraz z iloscia przebiegow algorytm jest co raz szybszy - gdyz do sprawdzenia ma mniej liczb
- kolejka q bedzie zawierac liczby pierwsze.
Jak to dziala?
do q wstawiamy pierwsza liczbe czyli np. 2 i usuwamy ja z p. Sprawdzamy czy kolejna liczba, np. 3 w p jest podzielna przez 2, nie jest wiec wstawiamy ja do w, i tak z kazda liczba w p. Przenosimy zawatosc w do p i od nowa, czyli przenosimy 3 do q. Sprawdzamy kolejna liczbe z p czy jest podzialna przez 3 - jezeli tak to do w, jezeli nie to kasacja...
pozdrawiam
0
jak stworzyć kolejke z elementami np od 2-100000 ??? rozumiem , że zamiast kolejki można też zastosować liste ??
0
chmmm. o ile mi wiadomo kolejka nie posiada jakiegos gornego ograniczenia w rozmiarze - z reszta jak kazda struktura dynamiczna - polecam przejrzec moj program rozwiazujacy ten problem - jest w dziale kody zrodlowe/pascal - to wyjasni wszystko...
0
Nie znam sie na Pascalu [glowa] . Oczywiście , że nie posiada ograniczenia , ograniczeniem jest tylko pamięć jaką może przydziielić komputer . Rozumiem , ze zrobimy sobie strukture , ktroaz zawiera wartość { int } , oraz wskaźnik do następnego i ewentualnie poprzedniego elementyu tej dynamicznej struktury danych . A nastepnie w petli odpowiednia ilość razy , będziemy dodawać do tej struktury ( kolejki , listy ) następny element , czyli wcześniej ostatni element nie będzie już wskazywał na NULL , tylko na ten element który dodaliśmy , a nowo dodany element bedzie teraz wskazywal na NULL , i bedzie zawieral wartość o 1 większą od poprzedniego ? I tak ile razy chcemy . Ale problem polega w tym , że jeden element takiej struktury będzie zawierał 3 razy więcej miejsca ( int , int* , int* , o ile int* zajmuje tyle co int , nie pamiętam ) niż jeden element tablicy ( int ) . Więc niekoniecznie rozwiązanie ze struktura będzie lepsze , moze sie okazać , że utworzymy dłuższą tablice niż kolejke . Ale z drugiej strony tworząc tablice musimy jej przydzielić CIĄGŁĄ część pamięci , czyli taką np że elementy tablicy mają zarezerwowane komórki pamięci od 10000-100000 , czykli komórki pamięci dla tablicy musza być obok siebie pokolei , nie wiem jak to ładnie powiedzieć [glowa]
0
jednakze przewaga struktury dynamicznej jest to ze nie musisz deklarowacjej rozmiaru. Deklarujac tablice moze okazac sie ze jest ona za mala, lub tez za duza (w przypadku np 1000000 elementowejtablicy, gdzie faktycznie wykorzystamy TYLKO 10 komorek... - reszta to tylko zawalanie pamieci smieciami, natomiast struktura dynamiczna rezerwuje tylko tyle pamieci ile potrzebuje)..
0
od tego właśnie są tablice dynamiczne ( new , malloc )