Ĺadny brzuch
Jezeli mam program, w ktorym mam sprawdzac liczby pierwsze, maksymalna bedzie powiedzmy wielkosci 2^26 to lepiej sobie zapisac wszystkie liczby z tego zakresu tj do pierwiastka kwadratowego z tej liczby, czy sprawdzac na bierząco sitem? ;) Takie troche chyba glupie pytanie ;]
nie za bardzo zrozumiałem Twoje pytanie. jeśli chcesz napisać program który znajdzie wszystkie liczby pierwsze z pewnego zakresu to wystarczy zaimplementować sito erastotenesa. spróbuj napisać dokładnie o co Ci chodzi i może też wspomnij w jakim języku programowania ma to być napisane (chyba że chodzi tu tylko o jakiś algorytm)
:)
nie za bardzo zrozumiałem Twoje pytanie. jeśli chcesz napisać program który znajdzie wszystkie liczby pierwsze z pewnego zakresu to wystarczy zaimplementować sito erastotenesa. spróbuj napisać dokładnie o co Ci chodzi i może też wspomnij w jakim języku programowania ma to być napisane (chyba że chodzi tu tylko o jakiś algorytm)
:)
Ja znam jeden sposob na wybranie liczby piwerwszej i polega on an podzieleniu liczby, którą sprawdzamy czy jest pierwsza przy pomocy pętli przez wszystki od 2 az do niej samej. Znam tylko taki sposób długi ale na 100% dobry:)
chyba o to Ci chodzilo:>
Tez go znam ;) Ok, temat zamkniety wiem juz ;]
no jeśli bardzo zależy Ci na szybkości i mniej więcej wiesz jakiego zakresu liczb można się spodziewać, to można najpierw wygenerować sobie tablicę z liczbami pierwszymi, załączyć taką tablicę do projektu, a potem żeby sprawdzić czy wpisana liczba jest liczbą pierwszą wystarczy tylkio przeszukać tablicę, najlepiej przewszukiwaniem binarnym (złożoność logarytmiczna) :)
// no i nie zdążyłem napisać ;)
Użytkownik Kabar edytował ten post 19 marzec 2006, 00:25
Szybkosc jest tu glownym priorytetem ;] Moze ma ktos jakies inne pomysly jak to szybko sprawdzic?
Użytkownik snakeomeister edytował ten post 19 marzec 2006, 00:37
Tak jak napisał Kabar, tylko że lepiej byłoby to wgrać do na przykład drzewa TRIE. A jeśli chcesz poznać inne sposoby sprawdzania czy liczba jest pierwsza to możesz zajrzeć na tą stronę.
Poza tym możesz tam znaleźć listę liczb pierwszych, którą będziesz mógł wczytywać na starcie.
Użytkownik Chmurek edytował ten post 19 marzec 2006, 12:13
Tak. Propabilistyczny test Millera-Rabina i tablica liczb Carmichaela. Odsylam do [1].
[1]. T. H. Cormen, C. E. Leiserson, R. L. Rivest "Wprowadzenie do algorytmow".
Test Millera-Rabina jest świetny, sprawdza bardzo szybko nawet kilkusetcyfrowe liczby :)
Tylko że nie daje pewnej odpowiedzi czy liczba jest pierwsza, więc raczej się nie nadaje tutaj. ;)
Ale prawdopodobienstwo ze liczba nie jest pierwsza wynosi 1/4^n, n>50 czyli mniejsze od 1/10^30, czyli bardzo małe. W sumie mozna iles tam liczb wpisac do tablicy albo do BST wrzucic.
Ja bym jednak był zdecydowanie za TRIE słownikowym na przykład takim, w którym słowami byłyby liczby zapisane w systemie binarnym. Takie drzewo byłoby zarówno o wiele mniejsze od BST jak i o wiele szybsze.
Ale czy to nie jest tak, ze test Millera moze sie mylic jedynie w wypadku liczb Carmichaela? A tych liczb jest bardzo malo (w podanym zakresie), mozna trzymac je w tablicy i sprawdzac.
Użytkownik marcepanowy_kapturek edytował ten post 19 marzec 2006, 14:10
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
nie za bardzo zrozumiałem Twoje pytanie. jeśli chcesz napisać program który znajdzie wszystkie liczby pierwsze z pewnego zakresu to wystarczy zaimplementować sito erastotenesa. spróbuj napisać dokładnie o co Ci chodzi i może też wspomnij w jakim języku programowania ma to być napisane (chyba że chodzi tu tylko o jakiś algorytm)
:)
nie za bardzo zrozumiałem Twoje pytanie. jeśli chcesz napisać program który znajdzie wszystkie liczby pierwsze z pewnego zakresu to wystarczy zaimplementować sito erastotenesa. spróbuj napisać dokładnie o co Ci chodzi i może też wspomnij w jakim języku programowania ma to być napisane (chyba że chodzi tu tylko o jakiś algorytm)
:)
Ja znam jeden sposob na wybranie liczby piwerwszej i polega on an podzieleniu liczby, którą sprawdzamy czy jest pierwsza przy pomocy pętli przez wszystki od 2 az do niej samej. Znam tylko taki sposób długi ale na 100% dobry:)
chyba o to Ci chodzilo:>
Tez go znam ;) Ok, temat zamkniety wiem juz ;]
no jeśli bardzo zależy Ci na szybkości i mniej więcej wiesz jakiego zakresu liczb można się spodziewać, to można najpierw wygenerować sobie tablicę z liczbami pierwszymi, załączyć taką tablicę do projektu, a potem żeby sprawdzić czy wpisana liczba jest liczbą pierwszą wystarczy tylkio przeszukać tablicę, najlepiej przewszukiwaniem binarnym (złożoność logarytmiczna) :)
// no i nie zdążyłem napisać ;)
Użytkownik Kabar edytował ten post 19 marzec 2006, 00:25
Szybkosc jest tu glownym priorytetem ;] Moze ma ktos jakies inne pomysly jak to szybko sprawdzic?
Użytkownik snakeomeister edytował ten post 19 marzec 2006, 00:37
Tak jak napisał Kabar, tylko że lepiej byłoby to wgrać do na przykład drzewa TRIE. A jeśli chcesz poznać inne sposoby sprawdzania czy liczba jest pierwsza to możesz zajrzeć na tą stronę.
Poza tym możesz tam znaleźć listę liczb pierwszych, którą będziesz mógł wczytywać na starcie.
Użytkownik Chmurek edytował ten post 19 marzec 2006, 12:13
Tak. Propabilistyczny test Millera-Rabina i tablica liczb Carmichaela. Odsylam do [1].
[1]. T. H. Cormen, C. E. Leiserson, R. L. Rivest "Wprowadzenie do algorytmow".
Test Millera-Rabina jest świetny, sprawdza bardzo szybko nawet kilkusetcyfrowe liczby :)
Tylko że nie daje pewnej odpowiedzi czy liczba jest pierwsza, więc raczej się nie nadaje tutaj. ;)
Ale prawdopodobienstwo ze liczba nie jest pierwsza wynosi 1/4^n, n>50 czyli mniejsze od 1/10^30, czyli bardzo małe. W sumie mozna iles tam liczb wpisac do tablicy albo do BST wrzucic.
Ja bym jednak był zdecydowanie za TRIE słownikowym na przykład takim, w którym słowami byłyby liczby zapisane w systemie binarnym. Takie drzewo byłoby zarówno o wiele mniejsze od BST jak i o wiele szybsze.
Ale czy to nie jest tak, ze test Millera moze sie mylic jedynie w wypadku liczb Carmichaela? A tych liczb jest bardzo malo (w podanym zakresie), mozna trzymac je w tablicy i sprawdzac.
Użytkownik marcepanowy_kapturek edytował ten post 19 marzec 2006, 14:10