Macie moze jakis pomysl jak napisac cos takiegoby program wydukowal kolejne liczby pierwsze. Jak w ogóle moge zdefiniowac w Delphi liczby pierwsze?
--
pozdr.
Y@siu
0
0
Może cos takiego:
:labelik
for I:= n to m do begin
a:=I;
for b:=n to a do begin
liczba:=a/n
if liczba 1 then
if liczba liczba then
goto labelik
czy cos takiego, ale to chyba nie będzie za szybkie...
--
Uwielbiam programować
W razie problemu, ksišżka pomoże
0
To znaczy proponujesz dzielic w kolko by sprawdzic czy liczba jest podzielna przez cos innego niz siebie sama i jeden. To w sumie jest sposob. Ale przydalo by sie cos szybszego...
--
pozdr.
Y@siu
0
Moze powiem dokladniej o co mi chodzi. Musze w programie wydrukowac dwadziescia najmniejszych liczb pierwszych. A w zasadzie musze wyliczyc ich sume...
A i przy okzaji cos jeszcze. Jak policzyc ile cyfr ma dana liczba na przyklad integer. Tzn. liczby te sa na pewno liczbami calkowitymi.
--
pozdr.
Y@siu
0
Lepiej dzielic do
__
\/X '
Bo to da tylko log z x mozliwosci
--
"I think I'm Dumb, maybe just happy"
0
Na mojej stronce http://www.vogel.pascal.prv.pl znajduje się ultraszybki algorym znajdywania liczb pierwszych.
Co do drugiego pytania:
if l mniejsze 10 then .. else
if l mniejsze 100 then .. else
if l mniejsze 1000 then .. else
Ewentualnie:
Length(IntToStr(l))
--
Vogel [Delphi 6 PE]
Life is just a dream, you know...
[Cowboy Bebop]
0
Najszybszy sposób znajdowania liczb pierwszych z zadanego przedziału to Sito Erastotenesa.
W kilku innych przypadkach można to trochę zmodyfikować, żeby działało jeszcze szybciej. Najszybszy sposób znajdowania NWD (co się łaczy z liczbami pierwszymi) to oczywiście algorytm Euklidesa.
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers.net
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
0
Najszybszy sposób znajdowania liczb pierwszych z zadanego przedziału to Sito Erastotenesa.
To właśnie jest na mojej stronce :)
--
Vogel [Delphi 6 PE]
Life is just a dream, you know...
[Cowboy Bebop]
0
Dzieki. O co takiego wlasnie mi chodzilo. Wymagalo to malej przerobki na potrzeby zadania (tylko suma 20 najmniejszych liczb pierwszych jest mi potrzebna). A oto ten algorytm po mojeje przerobce:
var
Tablica: array[2..72] of Boolean;
a, c, j, suma, check: Integer;
begin
suma := 0;
check := 0;
for j:=2 to 72 do Tablica[j]:=True;
a:=2;
while a [i]mniejsze[/i] 72 do begin
if not Tablica[a] then begin
Inc(a);
Continue { ominięcie dzielników już sprawdzonych }
end;
c:=a shl 1;
while c [i]mniejsze równe[/i] 72 do begin
Tablica[c]:=False;
Inc(b, a)
end;
Inc(a)
end;
for i:=2 to 72 do if Tablica[j] then
begin
check:= check+1;
if check [i]mniejsze[/i] 21 then
begin
suma:=suma+i;
Label1.Caption:=inttostr(suma);
end;
end;
Jeszcze raz dzieki!
--
pozdr.
Y@siu
0
[niewinnosc] Macie chyba na myśli
sito Eratostenesa
(a nie Erastotenesa).
Jest to faktycznie metoda szybka, ale ma pewną zasadniczą wadę (powiem o niej później), która powoduje, że czasami nie można z poniżeszego algorytmu zrobić wielkiego użytku:
- Liczby od 1 do N zapisujemy w porządku rosnącym
- Pierwsza liczba to 2. Skreślamy wszystkie jej wielokrotności
- Bierzemy pierwszą nie skreśloną liczbę i znów skreślamy jej wielokrotności
Na koniec w naszej tabelce zostają same liczby pierwsze.
Wadą tej metody jest to, że musimy z góry określić jak wielkie ma być N. Powiedzmy, że chcemy podać pierwsze 80 liczb pierwszych, jakie N mamy dobrać? Oczywiscie bardzo pomocna byłaby taka funkcja f(n), która dla danej wartości n zwraca ilość liczb pierwszych mniejszych od n. Niestety do dziś nie wiadomo, czy taka zależność istnieje (jest to jeden z otwartych problemów teorii liczb).
Dlatego prawdopodobnie użyteczniejszy jest inny sposób, co prawda o wiele wolniejszy (jego złożoność obliczeniowa jest wykładnicza, a dla porównania złożoność sita Eratostenesa jest wielomianowa, konkretnie O(n^2)), niemniej wystarczająco szybki aby podać 10000 liczb pierwszych w rozsądnym czasie:
- Niech p będzie tablicą liczb i pierwsze dwa elementy niech będą równe 1,2.
- n=3
- jeśli n nie jest podzielne przez liczby z ciągu p to dopisz n do tego ciagu (jest to kolejna liczba pierwsza)
- n=n+2 (nie ma sensu sprawdzać liczb parzystych większych od 2)
- Wróć do 3.
Oczywiście powyższy algorytm nigdy się nie zatrzyma, niemniej odpowiednie zmodyfikowanie tego schematu aby miał właściwość stopu nie powinno sprawić większego problemu przeciętnemu programiście.
(ewentualnie mogę udostępnić kod napisany w języku REXX)
Jest jeszcze jeden arcy-ciekawy algorytm, który odpowiada na pytanie "Czy podana wartość jest liczbą pierwszą", w matematyce nazywa się go testem Rabina i ma on bardzo ciekawą własność - podaje odpowiedź z pewnym określonym prawdopodobieństwem.
Ścisła strona matematyczna tego zagadnienia zniechęca (mogę ją udostępnić, jeśli ktoś jest szczególnie ciekaw), ogólnie można powiedzieć, że mamy do dyspozycji funkcję P(x) która używa pewnego testu aby sprawdzić czy argument x jest liczbą pierwszą i może ona "odpowiadać" na dwa sposoby:
- Podana liczba nie jest liczbą pierwszą na pewno
- Podana liczba jest liczbą pierwszą na 75% (czyli z prawdopodobieństwem błedu 25%)
Czy 75% wystarczy? Jeśli (słusznie) odczuwasz że jest to trochę za mało (bo oznacza to, że raz na cztery odpowiedź będzie błędna) to możesz zwiększyć swoje szanse stosując tą metodę ponownie. Jeśli zastosujesz ją drugi raz, to prawdopodobieństwo popełnienia błędu wynosi 25%*25% czyli 6.25% (czyli na 93.75% nasza odpowiedź jest poprawna).
Ostatni algorytm należy do klasy tak zwanych algorytmów probabilistycznych i często jest jedynym sensownym rozwiązaniem gdy złożoność obliczeniowa problemu jest przytłaczająca. Podany tu algorytm ma liniową złożoność obliczeniową, a wielokrotnie stosując test P(x) (na przykład 100 razy) prawdopodobieństwo wystąpienia błędnej odpowiedzi staje się mniejsze od prawdopodobieństwa że procesor podczas obliczeń popełni błąd (na marginesie: zdarza się to niezwykle rzadko).
Pozdrawiam [niewinnosc]
0
- Pierwsza liczba to 2. Skreślamy wszystkie jej wielokrotności
A 1 to co,poszło do lasu.
--
Carl Friedrich Gauss(1777-1855) - Niemiec, książe matematyków
0
- Pierwsza liczba to 2. Skreślamy wszystkie jej wielokrotności
A 1 to co,poszło do lasu.
Według wielu matematyków 1 nie jest liczbą pierwszą (przydaje się to często przy definiowaniu problemów. Nie trzeba wykluczać 1). To jest problem taki sam jak: "Czy 0 jest liczbą naturalną". Ja bym się nie czepiał.
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers.net
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
0
Macie chyba na myśli
sito Eratostenesa
(a nie Erastotenesa).
Zgadza się. Pomyłka.
(ewentualnie mogę udostępnić kod napisany w języku REXX)
Mam gdzieś taki w Delphi (ktoś mi kiedyś przysłał)
Ścisła strona matematyczna tego zagadnienia zniechęca (mogę ją udostępnić, jeśli ktoś jest szczególnie ciekaw)
Nie byłbym sobą, gdybym tego nie zobaczył :) Jak możesz to wrzuć na maila.
Czy 75% wystarczy?
To i tak zawsze coś. Jeżeli nie mam 100% pewności to mogę to sprawdzić najgorszym z możliwych sposobów.
propabilistycznych
Chyba masz na myśli: "probablistycznych" :)
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers.net
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
0
Chyba masz na myśli: "probablistycznych" :)
To foróm dla programistoof, nie dla polonistówP
--
Vogel [Delphi 6 PE]
Life is just a dream, you know...
[Cowboy Bebop]
0
swiety napisał:
"Pierwsza liczba to 2. Skreślamy wszystkie jej wielokrotności "
A 1 to co,poszło do lasu.
Mam wrażenie że zbyt długo się nie zastanowiałeś zanim napisałeś te słowa. Przecież KAŻDA liczba naturalna jest wielokrotnością jedynki (wynika to wprost z bardzo ciekawej konstrukcji zbioru liczb naturalnych trakrowanych jako kolejne wielokrotności jedynki),
więc jeśli mielibyśmy z tablicy liczb naturalnych mniejszych od n skreślić wszystkie wielokrotności jedynki to nic by nie pozostało (po za jedynką, której nie skreślamy).
Czy jedynka jest liczbą pierwszą? Najbardziej rozpowszechniona definicja liczb pierwszych jednoznacznie udziela na to odpowiedzi:
licznba naturalna p jest pierwszą, jeśli p>1 i jedynymi dzielnikami p są 1 i p.
Czyli 1 nie jest liczbą pierwszą (można się o tym przekonać sięgając do tablic liczb pierwszych, swoją drogą jak już tam będziecie spoglądać to zobaczcie ile cyfr ma największa poznana liczba pierwsza ...)
Wygląda więc na to że liczba 1 faktycznie poszła do lasu. (pytanie: którego? jest jednym z otwartych problemów teorii liczb hehe).
Skoro pojawił się maniak "księcia matematyków" Carla Friedricha Gaussa (poniekąd geodety) to warto chyba zaznaczyć, że Gauss wypowiedział pewną hipotezę: Ilość liczb pierwszych mniejszych od liczby x wynosi:
x / lnx.
Czyli dla x=1000 podstawiając do wzoru x / lnx otrzymujemy 144.7. Czyli według hipotezy Gaussa jest 145 liczb pierwszych mniejszych od 1000.
W rzeczywistości jest ich 168.
Nie jest to więc zależność ścisła (dlatego w poprzednim poście napisałem że prawdziwa zależność jest w istocie nieznana), niemniej daje pewne przybliżenie. Natomiast udowodniona jest (przez Poussina) asymptotyczność tej hipotezy, czyli:
"Podstawowe twierdzenie teorii liczb"
Lim x->infinite [ F(x) / (x / lnx) ] = 1.
gdzie F(x) oznacza ilość liczb pierwszych mniejszych od x.
Co oznacza że x / lnx zbliża się do F(x) dla (nieskończenie) dużych x.
Dryobates masz rację, oczywiście chodzi o "probabilistycznych" :-) :-) :-)
(Naturalnie podłożyłem się celowo, he he ...)
Zamieszczę ścisły wywód przykładowej (w rzeczywistości jest ich kilka) metody probabilistycznej jak będę miał dłuższą chwilę wolnego czasu (a zapewniam że zamieszczenie i zrozumienie tego wzoru zabierze trochę czasu).
Pamiętasz "metodę kongruencji liniowej" ? Tak się składa że Gauss jako pierwszy zrozumiał znaczenie pojęcia kongruencji (czyli przystawania modulo) i systematycznie je stosował.
Pozdrawiam
[niewinnosc]
0
licznba naturalna p jest pierwszą, jeśli p>1 i jedynymi dzielnikami p są 1 i p.
Powiedz to moim wykładowcom. Jednen twierdzi, że 1 jest liczbą pierwszą, a drugi że nie. U jednego trzeba mówić, że jest u drugiego, że nie :)
swoją drogą jak już tam będziecie spoglądać to zobaczcie ile cyfr ma największa poznana liczba pierwsza ...)
65050 cyfr (2^216091-1)
Czyli dla x=1000 podstawiając do wzoru x / lnx otrzymujemy 144.7. Czyli według hipotezy Gaussa jest 145 liczb pierwszych mniejszych od 1000.
W rzeczywistości jest ich 168.
I całe szczęście. Co by się stało z większością skutecznych obecnie szyfrów (tak jak też wzór Eulera (chyba) na liczby pierwsze i kilka innych prób znalezienia liczb pierwszych)
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers.net
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
0
Dryobates wskazał na następującą liczbę pierwszą:
65050 cyfr (2^216091-1)
Całkiem spora, ale mam dużo większą:
909526 cyfr (-1+2^3021377)
Została ona znaleziona w roku 1998 przy udziale tysięcy użytkowników internetu.
Pewnie od tamtego czasu zostało odnalezione coś większego ...