Artykuł dotyczy pojęć liczb pierwszych i złożonych. Podano definicje takich liczb wraz z przykładami. Dajemy dowód, że liczba liczb pierwszych jest nieograniczona i dokonujemy wpisu do tablicy liczb pierwszych metodą Eratostenesa. Podane zostaną dowody na to, czy liczba jest liczbą pierwszą, czy złożoną.
Yandex.RTB R-A-339285-1
Liczby pierwsze i złożone — definicje i przykłady
Liczby pierwsze i złożone są klasyfikowane jako liczby całkowite dodatnie. Muszą być większe niż jeden. Dzielniki dzielą się również na proste i złożone. Aby zrozumieć pojęcie liczb złożonych, należy najpierw przestudiować pojęcia dzielników i wielokrotności.
Definicja 1
Liczby pierwsze to liczby całkowite, które są większe niż jeden i mają dwa dodatnie dzielniki, czyli siebie i 1.
Definicja 2
Liczby złożone to liczby całkowite, które są większe niż jeden i mają co najmniej trzy dodatnie dzielniki.
Jeden nie jest ani liczbą pierwszą, ani liczbą złożoną. Ma tylko jeden dodatni dzielnik, więc różni się od wszystkich innych liczb dodatnich. Wszystkie liczby całkowite dodatnie nazywane są naturalnymi, to znaczy używanymi do liczenia.
Definicja 3
liczby pierwsze to liczby naturalne, które mają tylko dwa dodatnie dzielniki.
Definicja 4
Numer złożony jest liczbą naturalną, która ma więcej niż dwa dodatnie dzielniki.
Każda liczba większa niż 1 jest liczbą pierwszą lub złożoną. Z własności podzielności wynika, że 1 i liczba a zawsze będą dzielnikami dowolnej liczby a, to znaczy, że będzie podzielna sama przez siebie i przez 1. Podajemy definicję liczb całkowitych.
Definicja 5
Liczby naturalne, które nie są pierwsze, nazywane są liczbami złożonymi.
Liczby pierwsze: 2, 3, 11, 17, 131, 523. Są podzielne tylko przez siebie i przez 1. Liczby złożone: 6, 63, 121, 6697. Oznacza to, że liczbę 6 można rozłożyć na 2 i 3, a 63 na 1, 3, 7, 9, 21, 63 i 121 na 11, 11, czyli jej dzielniki będą wynosić 1, 11, 121. Liczba 6697 rozpadnie się na 37 i 181. Zauważ, że pojęcia liczb pierwszych i względnie pierwszych to różne pojęcia.
Aby ułatwić korzystanie z liczb pierwszych, musisz użyć tabeli:
Tabela dla wszystkich istniejących liczb naturalnych jest nierealna, ponieważ jest ich nieskończona liczba. Gdy liczby osiągną rozmiary 10000 lub 1000000000, warto pomyśleć o użyciu sita Eratostenesa.
Rozważ twierdzenie, które wyjaśnia ostatnie stwierdzenie.
Twierdzenie 1
Najmniejszy dodatni dzielnik liczby naturalnej większej niż 1 innej niż 1 jest liczbą pierwszą.
Dowód 1
Załóżmy, że a jest liczbą naturalną większą od 1, b jest najmniejszym niejednorodnym dzielnikiem a. Musimy udowodnić, że b jest liczbą pierwszą, używając metody sprzeczności.
Powiedzmy, że b jest liczbą złożoną. Stąd wynika, że istnieje dzielnik b , który jest różny od 1 i od b . Taki dzielnik jest oznaczony jako b 1 . Konieczne jest, aby warunek 1< b 1 < b została ukończona.
Widać to z warunku, że a jest podzielne przez b, b jest podzielne przez b 1, co oznacza, że pojęcie podzielności wyraża się w ten sposób: a = b q i b = b 1 q 1 , skąd a = b 1 (q 1 q) , gdzie q i q 1 są liczbami całkowitymi. Zgodnie z zasadą mnożenia liczb całkowitych iloczyn liczb całkowitych jest liczbą całkowitą o równości postaci a = b 1 · (q 1 · q) . Widać, że b 1 jest dzielnikiem a. Nierówność 1< b 1 < b nie pasuje, ponieważ otrzymujemy, że b jest najmniejszym dodatnim dzielnikiem a nie równym 1.
Twierdzenie 2
Liczb pierwszych jest nieskończenie wiele.
Dowód 2
Załóżmy, że bierzemy skończoną liczbę liczb naturalnych n i oznaczamy je jako p 1 , p 2 , … , p n . Rozważmy wariant znalezienia liczby pierwszej innej niż wskazane.
Rozważmy liczbę p, która jest równa p 1 , p 2 , … , p n + 1 . Nie równa się każdej z liczb odpowiadających liczbom pierwszym postaci p 1 , p 2 , … , p n . Liczba p jest pierwsza. Wtedy twierdzenie uważa się za udowodnione. Jeśli jest złożony, to musimy przyjąć notację p n + 1 i pokaż niezgodność dzielnika z dowolnym z p 1 , p 2 , … , p n .
Gdyby tak nie było, to na podstawie własności podzielności iloczynu p 1 , p 2 , … , p n , otrzymujemy, że byłaby podzielna przez p n + 1 . Zauważ, że wyrażenie p n + 1 podzielona liczba p równa się sumie p 1 , p 2 , … , p n + 1 . Otrzymujemy, że wyrażenie p n + 1 należy podzielić drugi wyraz tej sumy, równy 1, ale jest to niemożliwe.
Widać, że dowolną liczbę pierwszą można znaleźć wśród dowolnej liczby podanych liczb pierwszych. Wynika z tego, że jest nieskończenie wiele liczb pierwszych.
Ponieważ istnieje wiele liczb pierwszych, tabele są ograniczone do liczb 100, 1000, 10000 i tak dalej.
Tworząc tablicę liczb pierwszych należy wziąć pod uwagę fakt, że takie zadanie wymaga sekwencyjnego sprawdzania liczb, zaczynając od 2 do 100. Jeśli nie ma dzielnika, jest on zapisywany w tabeli, jeśli jest złożony, to nie jest wprowadzany do tabeli.
Rozważmy krok po kroku.
Jeśli zaczniesz od liczby 2, to ma ona tylko 2 dzielniki: 2 i 1, co oznacza, że można ją wpisać do tabeli. Również z numerem 3 . Liczba 4 jest złożona, należy ją rozłożyć na 2 i 2. Liczba 5 jest liczbą pierwszą, co oznacza, że można ją ustalić w tabeli. Zrób to do liczby 100.
Ta metoda jest niewygodna i czasochłonna. Możesz zrobić stół, ale będziesz musiał poświęcić dużo czasu. Konieczne jest zastosowanie kryteriów podzielności, które przyspieszą proces znajdowania dzielników.
Za najwygodniejszą uważa się metodę wykorzystującą sito Eratostenesa. Rzućmy okiem na poniższe tabele. Na początek zapisuje się liczby 2, 3, 4, ..., 50.
Teraz musisz wykreślić wszystkie liczby będące wielokrotnościami 2. Dokonaj kolejnego przekreślenia. Otrzymujemy tabelę postaci:
Przejdźmy do wykreślania liczb będących wielokrotnościami 5. Otrzymujemy:
Wykreślamy liczby będące wielokrotnościami 7, 11. Wreszcie stół wygląda jak
Przejdźmy do sformułowania twierdzenia.
Twierdzenie 3
Najmniejszy dodatni dzielnik liczby podstawowej a nie przekracza a , gdzie a jest pierwiastkiem arytmetycznym danej liczby.
Dowód 3
Konieczne jest oznaczenie b jako najmniejszego dzielnika liczby złożonej a. Istnieje liczba całkowita q , gdzie a = b · q , i mamy b ≤ q . Nierówność formy b > q ponieważ warunek jest naruszony. Obie strony nierówności b ≤ q należy pomnożyć przez dowolną liczbę dodatnią b nie równą 1 . Otrzymujemy, że b b ≤ b q , gdzie b 2 ≤ a i b ≤ a .
Z udowodnionego twierdzenia wynika, że skreślenie liczb w tabeli prowadzi do tego, że konieczne jest rozpoczęcie od liczby równej b 2 i spełniającej nierówność b 2 ≤ a . Oznacza to, że jeśli wykreślisz liczby, które są wielokrotnościami 2, proces zaczyna się od 4, a te, które są wielokrotnościami 3, zaczynają się od 9 i tak dalej, aż do 100.
Kompilacja takiej tabeli przy użyciu twierdzenia Eratostenesa mówi, że po przekreśleniu wszystkich liczb złożonych pozostaną liczby pierwsze, które nie przekraczają n. W przykładzie, w którym n = 50 , mamy n = 50 . Stąd otrzymujemy, że sito Eratostenesa odsiewa wszystkie liczby złożone, które nie mają większej wartości niż wartość pierwiastka 50. Wyszukiwanie numerów odbywa się przez przekreślenie.
Przed rozwiązaniem konieczne jest ustalenie, czy liczba jest liczbą pierwszą czy złożoną. Często stosuje się kryteria podzielności. Spójrzmy na to w poniższym przykładzie.
Przykład 1
Udowodnij, że 898989898989898989 jest liczbą złożoną.
Rozwiązanie
Suma cyfr podanej liczby to 9 8 + 9 9 = 9 17 . Tak więc liczba 9 17 jest podzielna przez 9, na podstawie znaku podzielności przez 9. Wynika z tego, że jest złożony.
Takie znaki nie są w stanie udowodnić pierwszości liczby. Jeśli potrzebna jest weryfikacja, należy podjąć inne kroki. Najodpowiedniejszym sposobem jest wyliczanie liczb. W trakcie procesu można znaleźć liczby pierwsze i złożone. Oznacza to, że liczby w wartości nie powinny przekraczać a . Oznacza to, że liczba a musi zostać rozłożona na czynniki pierwsze. jeśli to prawda, to liczbę a można uznać za pierwszą.
Przykład 2
Określ liczbę złożoną lub pierwszą 11723.
Rozwiązanie
Teraz musisz znaleźć wszystkie dzielniki dla liczby 11723. Trzeba ocenić 11723 .
Stąd widzimy, że 11723< 200 , то 200 2 = 40 000 , i 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
Aby dokładniej oszacować liczbę 11723, należy napisać wyrażenie 108 2 = 11 664, oraz 109 2 = 11 881 , następnie 108 2 < 11 723 < 109 2 . Wynika z tego, że 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Podczas dekompozycji otrzymujemy, że 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 to liczby pierwsze. Cały ten proces można przedstawić jako podział według kolumny. Oznacza to, że podziel 11723 przez 19. Liczba 19 jest jednym z jej czynników, ponieważ otrzymujemy dzielenie bez reszty. Przedstawmy podział według kolumny:
Wynika z tego, że 11723 jest liczbą złożoną, ponieważ oprócz siebie i 1 ma dzielnik 19 .
Odpowiadać: 11723 to liczba złożona.
Jeśli zauważysz błąd w tekście, zaznacz go i naciśnij Ctrl+Enter
W tym artykule będziemy się uczyć liczby pierwsze i złożone. Najpierw podajemy definicje liczb pierwszych i złożonych, a także podajemy przykłady. Następnie dowodzimy, że jest nieskończenie wiele liczb pierwszych. Następnie napiszemy tablicę liczb pierwszych i rozważymy metody tworzenia tablicy liczb pierwszych, szczególnie uważnie przyjrzymy się metodzie zwanej sitem Eratostenesa. Podsumowując, podkreślamy główne punkty, które należy wziąć pod uwagę, udowadniając, że dana liczba jest liczbą pierwszą lub złożoną.
Nawigacja po stronach.
Liczby pierwsze i złożone — definicje i przykłady
Pojęcia liczb pierwszych i liczb złożonych odnoszą się do tych, które są większe niż jeden. Takie liczby całkowite, w zależności od liczby ich dodatnich dzielników, dzielą się na liczby pierwsze i złożone. Więc żeby zrozumieć definicje liczb pierwszych i złożonych, musisz dobrze wiedzieć, jakie są dzielniki i wielokrotności.
Definicja.
liczby pierwsze są liczbami całkowitymi większymi niż jeden, które mają tylko dwa dodatnie dzielniki, a mianowicie siebie i 1 .
Definicja.
Liczby złożone są liczbami całkowitymi większymi niż jeden, które mają co najmniej trzy dodatnie dzielniki.
Oddzielnie zauważamy, że liczba 1 nie dotyczy liczb pierwszych ani złożonych. Jednostka ma tylko jeden dodatni dzielnik, którym jest sama liczba 1. To odróżnia liczbę 1 od wszystkich innych dodatnich liczb całkowitych, które mają co najmniej dwa dodatnie dzielniki.
Biorąc pod uwagę, że liczby całkowite dodatnie to , a jednostka ma tylko jeden dodatni dzielnik, można podać inne sformułowania dźwięcznych definicji liczb pierwszych i złożonych.
Definicja.
liczby pierwsze to liczby naturalne, które mają tylko dwa dodatnie dzielniki.
Definicja.
Liczby złożone to liczby naturalne, które mają więcej niż dwa dodatnie dzielniki.
Zauważ, że każda dodatnia liczba całkowita większa niż jeden jest albo liczbą pierwszą, albo liczbą złożoną. Innymi słowy, nie ma ani jednej liczby całkowitej, która nie byłaby ani pierwsza, ani złożona. Wynika to z własności podzielności, która mówi, że liczby 1 i a są zawsze dzielnikami dowolnej liczby całkowitej a.
Na podstawie informacji zawartych w poprzednim akapicie możemy podać następującą definicję liczb złożonych.
Definicja.
Liczby naturalne, które nie są pierwsze, są nazywane składnik.
Przynieśmy przykłady liczb pierwszych i złożonych.
Jako przykłady liczb złożonych podajemy 6 , 63 , 121 i 6697 . To stwierdzenie również wymaga wyjaśnienia. Liczba 6, oprócz dodatnich dzielników 1 i 6, ma również dzielniki 2 i 3, ponieważ 6 \u003d 2 3, więc 6 jest naprawdę liczbą złożoną. Dodatnimi dzielnikami 63 są liczby 1 , 3 , 7 , 9 , 21 i 63 . Liczba 121 jest równa iloczynowi 11 11 , więc jej dodatnie dzielniki to 1 , 11 i 121 . A liczba 6697 jest złożona, ponieważ jej dodatnimi dzielnikami oprócz 1 i 6697 są również liczby 37 i 181.
Kończąc ten akapit, chciałbym również zwrócić uwagę na fakt, że liczby pierwsze i względnie pierwsze są dalekie od tego samego.
Tabela liczb pierwszych
Liczby pierwsze, dla wygody ich dalszego wykorzystania, zapisywane są w tabeli zwanej tabelą liczb pierwszych. Poniżej jest tablica liczb pierwszych do 1 000 .
Powstaje logiczne pytanie: „Dlaczego wypełniliśmy tablicę liczb pierwszych tylko do 1000, czy nie jest możliwe zrobienie tablicy wszystkich istniejących liczb pierwszych”?
Odpowiedzmy najpierw na pierwszą część tego pytania. W przypadku większości problemów, które dotyczą liczb pierwszych, wystarczą liczby pierwsze do tysiąca. W innych przypadkach najprawdopodobniej będziesz musiał skorzystać ze specjalnych technik rozwiązywania problemów. Chociaż oczywiście możemy tablicować liczby pierwsze aż do dowolnie dużej skończonej dodatniej liczby całkowitej, czy to 10 000 czy 1 000 000 000 , w następnym akapicie omówimy metody kompilacji tablic liczb pierwszych, w szczególności przeanalizujemy metodę nazywa.
Przyjrzyjmy się teraz możliwości (a raczej niemożliwości) skompilowania tablicy wszystkich istniejących liczb pierwszych. Nie możemy stworzyć tabeli wszystkich liczb pierwszych, ponieważ jest nieskończenie wiele liczb pierwszych. Ostatnie stwierdzenie to twierdzenie, które udowodnimy po następującym twierdzeniu pomocniczym.
Twierdzenie.
Najmniejszy dodatni dzielnik liczby naturalnej większej niż 1 innej niż 1 jest liczbą pierwszą.
Dowód.
Wynajmować a jest liczbą naturalną większą niż jeden, a b jest najmniej dodatnim dzielnikiem a. Udowodnijmy, że b jest liczbą pierwszą przez sprzeczność.
Załóżmy, że b jest liczbą złożoną. Następnie istnieje dzielnik liczby b (oznaczmy ją jako b 1 ), który jest różny od 1 i b . Jeśli weźmiemy również pod uwagę, że wartość bezwzględna dzielnika nie przekracza wartości bezwzględnej dzielnej (wiemy to z własności podzielności), to warunek 1
Ponieważ liczba a jest podzielna przez b przez warunek, a powiedzieliśmy, że b jest podzielne przez b 1 , to pojęcie podzielności pozwala nam mówić o istnieniu takich liczb całkowitych q i q 1, że a=b q i b=b 1 q 1 , gdzie a= b 1 • (q 1 • q). Z tego wynika, że iloczyn dwóch liczb całkowitych jest liczbą całkowitą, to równość a=b 1 ·(q 1 ·q) wskazuje, że b 1 jest dzielnikiem liczby a . Biorąc pod uwagę powyższe nierówności 1
Teraz możemy udowodnić, że jest nieskończenie wiele liczb pierwszych.
Twierdzenie.
Liczb pierwszych jest nieskończenie wiele.
Dowód.
Załóżmy, że tak nie jest. To znaczy, załóżmy, że istnieje tylko n liczb pierwszych, a te liczby to p 1 , p 2 , …, p n . Pokażmy, że zawsze możemy znaleźć liczbę pierwszą inną niż wskazane.
Rozważ liczbę p równą p 1 ·p 2 ·…·p n +1 . Jest jasne, że liczba ta różni się od każdej z liczb pierwszych p 1 , p 2 , …, p n . Jeśli liczba p jest pierwsza, to twierdzenie jest udowodnione. Jeżeli liczba ta jest złożona, to na mocy poprzedniego twierdzenia istnieje dzielnik pierwszy tej liczby (oznaczmy ją jako p n+1 ). Pokażmy, że ten dzielnik nie pokrywa się z żadną z liczb p 1 , p 2 , …, p n .
Gdyby tak nie było, to z własności podzielności iloczyn p 1 ·p 2 ·…·p n byłby podzielny przez p n+1 . Ale liczba p jest również podzielna przez p n+1, równą sumie p 1 ·p 2 ·…·p n +1. Oznacza to, że drugi wyraz tej sumy, równy jeden, musi być podzielny przez p n+1, a to jest niemożliwe.
W ten sposób udowodniono, że zawsze można znaleźć nową liczbę pierwszą, która nie jest zawarta wśród żadnej liczby liczb pierwszych podanych z góry. Dlatego istnieje nieskończenie wiele liczb pierwszych.
Czyli ze względu na to, że liczb pierwszych jest nieskończenie wiele, kompilując tablice liczb pierwszych, zawsze ograniczają się od góry do jakiejś liczby, zwykle 100, 1000, 10 000 itd.
Sito Eratostenesa
Teraz omówimy sposoby kompilowania tablic liczb pierwszych. Załóżmy, że musimy stworzyć tablicę liczb pierwszych do 100 .
Najbardziej oczywistą metodą rozwiązania tego problemu jest sekwencyjne sprawdzanie dodatnich liczb całkowitych, zaczynając od 2 i kończąc na 100 , pod kątem obecności dodatniego dzielnika, który jest większy niż 1 i mniejszy niż sprawdzana liczba (z właściwości podzielności wiedzieć, że wartość bezwzględna dzielnika nie przekracza wartości bezwzględnej dywidendy, różnej od zera). Jeżeli taki dzielnik nie zostanie znaleziony, to sprawdzana liczba jest liczbą pierwszą i jest ona wpisywana do tablicy liczb pierwszych. Jeżeli taki dzielnik zostanie znaleziony, to sprawdzana liczba jest złożona, NIE jest wpisywana do tablicy liczb pierwszych. Następnie następuje przejście do następnej liczby, która jest podobnie sprawdzana pod kątem obecności dzielnika.
Opiszmy kilka pierwszych kroków.
Zaczynamy od liczby 2. Liczba 2 nie ma dodatnich dzielników innych niż 1 i 2 . Jest to więc liczba pierwsza, dlatego wpisujemy ją do tabeli liczb pierwszych. Tutaj należy powiedzieć, że 2 to najmniejsza liczba pierwsza. Przejdźmy do numeru 3. Jego możliwym dodatnim dzielnikiem innym niż 1 i 3 jest 2 . Ale 3 nie jest podzielne przez 2, dlatego 3 jest liczbą pierwszą i trzeba ją również wpisać do tabeli liczb pierwszych. Przejdźmy do numeru 4. Jego dodatnie dzielniki inne niż 1 i 4 mogą wynosić 2 i 3 , sprawdźmy je. Liczba 4 jest podzielna przez 2, dlatego 4 jest liczbą złożoną i nie trzeba jej wpisywać do tabeli liczb pierwszych. Zauważ, że 4 to najmniejsza liczba złożona. Przejdźmy do numeru 5. Sprawdzamy, czy przynajmniej jedna z liczb 2 , 3 , 4 jest jego dzielnikiem. Ponieważ 5 nie jest podzielne przez 2, 3 lub 4, jest liczbą pierwszą i należy ją zapisać w tabeli liczb pierwszych. Następnie następuje przejście do liczb 6, 7 i tak dalej, aż do 100.
Takie podejście do kompilowania tabeli liczb pierwszych jest dalekie od ideału. Tak czy inaczej, ma prawo do istnienia. Zauważ, że przy tej metodzie konstruowania tabeli liczb całkowitych możesz użyć kryteriów podzielności, co nieco przyspieszy proces znajdowania dzielników.
Istnieje wygodniejszy sposób skompilowania tablicy liczb pierwszych o nazwie . Obecne w nazwie słowo „sito” nie jest przypadkowe, gdyż działania tej metody pomagają niejako „przesiać” przez sito liczb całkowitych Eratostenesa, dużych jednostek, w celu oddzielenia prostych od złożonych.
Pokażmy sito Eratostenesa w akcji podczas kompilowania tabeli liczb pierwszych do 50.
Najpierw spisujemy liczby 2, 3, 4, ..., 50 w kolejności.
Pierwsza zapisana liczba 2 to liczba pierwsza. Teraz od liczby 2 przesuwamy się kolejno w prawo o dwie liczby i wykreślamy te liczby, aż dojdziemy do końca skompilowanej tabeli liczb. Zatem wszystkie liczby będące wielokrotnościami dwóch zostaną przekreślone.
Pierwsza nie przekreślona liczba po 2 to 3 . Ta liczba jest pierwsza. Teraz od cyfry 3 przesuwamy się kolejno w prawo o trzy cyfry (biorąc pod uwagę już przekreślone cyfry) i wykreślamy je. Tak więc wszystkie liczby będące wielokrotnościami trzech zostaną wykreślone.
Pierwsza nie przekreślona liczba po 3 to 5 . Ta liczba jest pierwsza. Teraz od liczby 5 przesuwamy się kolejno w prawo o 5 liczb (uwzględniamy również przekreślone wcześniej liczby) i wykreślamy je. Tak więc wszystkie liczby będące wielokrotnościami pięciu zostaną wykreślone.
Następnie wykreślamy liczby będące wielokrotnościami 7, potem wielokrotnościami 11 i tak dalej. Proces kończy się, gdy nie ma już liczb do skreślenia. Poniżej znajduje się kompletna tabela liczb pierwszych do 50 uzyskanych przy użyciu sita Eratostenesa. Wszystkie nieprzekreślone liczby są liczbami pierwszymi, a wszystkie przekreślone liczby są złożone.
Sformułujmy i udowodnijmy twierdzenie, które przyspieszy proces tworzenia tablicy liczb pierwszych na sicie Eratostenesa.
Twierdzenie.
Najmniejszy niejednoznaczny dzielnik liczby złożonej a nie przekracza , gdzie jest od a .
Dowód.
Niech b oznacza najmniejszy dzielnik liczby złożonej a, który różni się od jedności (liczba b jest liczbą pierwszą, co wynika z twierdzenia udowodnionego na samym początku poprzedniego akapitu). Wtedy istnieje liczba całkowita q taka, że a=b q (tu q jest liczbą całkowitą dodatnią, która wynika z zasad mnożenia liczb całkowitych) oraz (gdy b>q, warunek, że b jest najmniejszym dzielnikiem a jest spełniony, ponieważ q jest również dzielnikiem a ze względu na równość a=q b ). Mnożąc obie strony nierówności przez dodatnią i większą od jednej liczby całkowitej b (możemy to zrobić), otrzymujemy , skąd i .
Co daje nam udowodnione twierdzenie o sicie Eratostenesa?
Po pierwsze, usuwanie liczb złożonych będących wielokrotnościami liczby pierwszej b powinno zaczynać się od liczby równej (wynika to z nierówności ). Na przykład skreślanie liczb będących wielokrotnościami dwóch powinno zaczynać się od liczby 4, wielokrotności trzech - od liczby 9, wielokrotności pięciu - od liczby 25 i tak dalej.
Po drugie, kompilację tablicy liczb pierwszych do liczby n za pomocą sita Eratostenesa można uznać za kompletną, gdy wszystkie liczby złożone, które są wielokrotnościami liczb pierwszych nieprzekraczających, są przekreślone. W naszym przykładzie n=50 (ponieważ zestawiamy liczby pierwsze do 50 ) i , więc sito Eratostenesa musi usunąć wszystkie złożone wielokrotności liczb pierwszych 2 , 3 , 5 i 7 , które nie przekraczają arytmetycznego pierwiastka kwadratowego z 50 . Oznacza to, że nie musimy już szukać i wykreślać liczb, które są wielokrotnościami liczb pierwszych 11 , 13 , 17 , 19 , 23 i tak dalej aż do 47 , ponieważ zostaną one już przekreślone jako wielokrotności mniejszych liczb pierwszych 2 , 3 , 5 i 7.
Czy to liczba pierwsza czy złożona?
Niektóre zadania wymagają sprawdzenia, czy dana liczba jest liczbą pierwszą czy złożoną. W ogólnym przypadku to zadanie nie jest proste, zwłaszcza w przypadku liczb, których zapis składa się ze znacznej liczby znaków. W większości przypadków musisz poszukać konkretnego sposobu na jego rozwiązanie. Postaramy się jednak nadać kierunek tokowi myślenia w prostych przypadkach.
Niewątpliwie można spróbować zastosować kryteria podzielności, aby udowodnić, że dana liczba jest złożona. Jeżeli na przykład jakieś kryterium podzielności wskazuje, że dana liczba jest podzielna przez jakąś dodatnią liczbę całkowitą większą od jeden, to pierwotna liczba jest złożona.
Przykład.
Udowodnij, że liczba 898 989 898 989 898 989 jest złożona.
Rozwiązanie.
Suma cyfr tej liczby to 9 8+9 9=9 17 . Ponieważ liczba równa 9 17 jest podzielna przez 9, to według kryterium podzielności przez 9 można argumentować, że pierwotna liczba jest również podzielna przez 9. Dlatego jest złożony.
Istotną wadą tego podejścia jest to, że kryteria podzielności nie pozwalają nam dowieść prostoty liczby. Dlatego sprawdzając liczbę pod kątem liczby pierwszej lub złożonej, należy postępować w inny sposób.
Najbardziej logicznym podejściem jest wyliczenie wszystkich możliwych dzielników danej liczby. Jeśli żaden z możliwych dzielników nie jest prawdziwym dzielnikiem danej liczby, to ta liczba jest liczbą pierwszą, w przeciwnym razie jest złożona. Z twierdzeń udowodnionych w poprzednim akapicie wynika, że dzielników danej liczby a należy szukać wśród liczb pierwszych nieprzekraczających . Tak więc podaną liczbę a można sukcesywnie podzielić przez liczby pierwsze (wygodne wzięcie z tablicy liczb pierwszych), próbując znaleźć dzielnik liczby a. Jeśli zostanie znaleziony dzielnik, liczba a jest złożona. Jeżeli wśród liczb pierwszych nieprzekraczających , nie ma dzielnika liczby a, to liczba a jest liczbą pierwszą.
Przykład.
Numer 11 723 proste czy złożone?
Rozwiązanie.
Dowiedzmy się, do jakiej liczby pierwszej mogą być dzielniki liczby 11 723. W tym celu szacujemy .
Jest całkiem oczywiste, że 
, od 200 2 \u003d 40 000 i 11 723<40 000
(при необходимости смотрите статью porównanie liczb). Zatem możliwe pierwsze dzielniki 11 723 są mniejsze niż 200. To już znacznie upraszcza nasze zadanie. Gdybyśmy tego nie wiedzieli, musielibyśmy posortować wszystkie liczby pierwsze nie do 200, ale do 11 723 .
W razie potrzeby możesz dokładniej oszacować. Ponieważ 108 2 \u003d 11 664 i 109 2 \u003d 11 881, a następnie 108 2<11 723<109 2
, следовательно, 
. Zatem każda z liczb pierwszych mniejszych niż 109 jest potencjalnie dzielnikiem pierwszym podanej liczby 11.723.
Teraz podzielimy kolejno liczbę 11 723 na liczby pierwsze 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Jeśli liczba 11 723 zostanie podzielona całkowicie przez jedną z zapisanych liczb pierwszych, to będzie złożona. Jeśli nie jest podzielna przez żadną z zapisanych liczb pierwszych, to pierwotna liczba jest liczbą pierwszą.
Nie będziemy opisywać całego tego monotonnego i monotonnego procesu podziału. Powiedzmy, że 11 723
Tablica liczb pierwszych od 1 do 10000. Tablica liczb pierwszych od 1 do 1000
Poniżej znajduje się tabela liczb pierwszych od 2 do 10000 (1229 sztuk). Jednostka nie jest wliczona w cenę, przepraszam. Niektórzy uważają, że jednostka nie jest wliczona w cenę, ponieważ… nie może tam być. " Liczba pierwsza to liczba, która ma dwa dzielniki: jeden i samą liczbę.„A liczba 1 ma tylko jeden dzielnik, nie dotyczy ani liczb pierwszych, ani złożonych. (Nota wyjaśniająca od Olgi z 21.09.12) Pamiętamy jednak, że liczby pierwsze są czasami wprowadzane w ten sposób: „ Liczba pierwsza to liczba podzielna przez jeden i przez samą siebie.„W tym przypadku jeden jest oczywiście liczbą pierwszą.
Tablica liczb pierwszych od 2 do 1000. Tablica liczb pierwszych od 2 do 1000 jest wyszarzona.
| 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 |
| 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
| 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 | 137 | 139 | 149 | 151 |
| 157 | 163 | 167 | 173 | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
| 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 | 281 |
| 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 | 349 | 353 | 359 |
| 367 | 373 | 379 | 383 | 389 | 397 | 401 | 409 | 419 | 421 | 431 | 433 |
| 439 | 443 | 449 | 457 | 461 | 463 | 467 | 479 | 487 | 491 | 499 | 503 |
| 509 | 521 | 523 | 541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 |
| 599 | 601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 | 659 |
| 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 | 733 | 739 | 743 |
| 751 | 757 | 761 | 769 | 773 | 787 | 797 | 809 | 811 | 821 | 823 | 827 |
| 829 | 839 | 853 | 857 | 859 | 863 | 877 | 881 | 883 | 887 | 907 | 911 |
| 919 | 929 | 937 | 941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 |
| 1009 | 1013 | 1019 | 1021 | 1031 | 1033 | 1039 | 1049 | 1051 | 1061 | 1063 | 1069 |
| 1087 | 1091 | 1093 | 1097 | 1103 | 1109 | 1117 | 1123 | 1129 | 1151 | 1153 | 1163 |
| 1171 | 1181 | 1187 | 1193 | 1201 | 1213 | 1217 | 1223 | 1229 | 1231 | 1237 | 1249 |
| 1259 | 1277 | 1279 | 1283 | 1289 | 1291 | 1297 | 1301 | 1303 | 1307 | 1319 | 1321 |
| 1327 | 1361 | 1367 | 1373 | 1381 | 1399 | 1409 | 1423 | 1427 | 1429 | 1433 | 1439 |
| 1447 | 1451 | 1453 | 1459 | 1471 | 1481 | 1483 | 1487 | 1489 | 1493 | 1499 | 1511 |
| 1523 | 1531 | 1543 | 1549 | 1553 | 1559 | 1567 | 1571 | 1579 | 1583 | 1597 | 1601 |
| 1607 | 1609 | 1613 | 1619 | 1621 | 1627 | 1637 | 1657 | 1663 | 1667 | 1669 | 1693 |
| 1697 | 1699 | 1709 | 1721 | 1723 | 1733 | 1741 | 1747 | 1753 | 1759 | 1777 | 1783 |
| 1787 | 1789 | 1801 | 1811 | 1823 | 1831 | 1847 | 1861 | 1867 | 1871 | 1873 | 1877 |
| 1879 | 1889 | 1901 | 1907 | 1913 | 1931 | 1933 | 1949 | 1951 | 1973 | 1979 | 1987 |
| 1993 | 1997 | 1999 | 2003 | 2011 | 2017 | 2027 | 2029 | 2039 | 2053 | 2063 | 2069 |
| 2081 | 2083 | 2087 | 2089 | 2099 | 2111 | 2113 | 2129 | 2131 | 2137 | 2141 | 2143 |
| 2153 | 2161 | 2179 | 2203 | 2207 | 2213 | 2221 | 2237 | 2239 | 2243 | 2251 | 2267 |
| 2269 | 2273 | 2281 | 2287 | 2293 | 2297 | 2309 | 2311 | 2333 | 2339 | 2341 | 2347 |
| 2351 | 2357 | 2371 | 2377 | 2381 | 2383 | 2389 | 2393 | 2399 | 2411 | 2417 | 2423 |
| 2437 | 2441 | 2447 | 2459 | 2467 | 2473 | 2477 | 2503 | 2521 | 2531 | 2539 | 2543 |
| 2549 | 2551 | 2557 | 2579 | 2591 | 2593 | 2609 | 2617 | 2621 | 2633 | 2647 | 2657 |
| 2659 | 2663 | 2671 | 2677 | 2683 | 2687 | 2689 | 2693 | 2699 | 2707 | 2711 | 2713 |
| 2719 | 2729 | 2731 | 2741 | 2749 | 2753 | 2767 | 2777 | 2789 | 2791 | 2797 | 2801 |
| 2803 | 2819 | 2833 | 2837 | 2843 | 2851 | 2857 | 2861 | 2879 | 2887 | 2897 | 2903 |
| 2909 | 2917 | 2927 | 2939 | 2953 | 2957 | 2963 | 2969 | 2971 | 2999 | 3001 | 3011 |
| 3019 | 3023 | 3037 | 3041 | 3049 | 3061 | 3067 | 3079 | 3083 | 3089 | 3109 | 3119 |
| 3121 | 3137 | 3163 | 3167 | 3169 | 3181 | 3187 | 3191 | 3203 | 3209 | 3217 | 3221 |
| 3229 | 3251 | 3253 | 3257 | 3259 | 3271 | 3299 | 3301 | 3307 | 3313 | 3319 | 3323 |
| 3329 | 3331 | 3343 | 3347 | 3359 | 3361 | 3371 | 3373 | 3389 | 3391 | 3407 | 3413 |
| 3433 | 3449 | 3457 | 3461 | 3463 | 3467 | 3469 | 3491 | 3499 | 3511 | 3517 | 3527 |
| 3529 | 3533 | 3539 | 3541 | 3547 | 3557 | 3559 | 3571 | 3581 | 3583 | 3593 | 3607 |
| 3613 | 3617 | 3623 | 3631 | 3637 | 3643 | 3659 | 3671 | 3673 | 3677 | 3691 | 3697 |
| 3701 | 3709 | 3719 | 3727 | 3733 | 3739 | 3761 | 3767 | 3769 | 3779 | 3793 | 3797 |
| 3803 | 3821 | 3823 | 3833 | 3847 | 3851 | 3853 | 3863 | 3877 | 3881 | 3889 | 3907 |
| 3911 | 3917 | 3919 | 3923 | 3929 | 3931 | 3943 | 3947 | 3967 | 3989 | 4001 | 4003 |
| 4007 | 4013 | 4019 | 4021 | 4027 | 4049 | 4051 | 4057 | 4073 | 4079 | 4091 | 4093 |
| 4099 | 4111 | 4127 | 4129 | 4133 | 4139 | 4153 | 4157 | 4159 | 4177 | 4201 | 4211 |
| 4217 | 4219 | 4229 | 4231 | 4241 | 4243 | 4253 | 4259 | 4261 | 4271 | 4273 | 4283 |
| 4289 | 4297 | 4327 | 4337 | 4339 | 4349 | 4357 | 4363 | 4373 | 4391 | 4397 | 4409 |
| 4421 | 4423 | 4441 | 4447 | 4451 | 4457 | 4463 | 4481 | 4483 | 4493 | 4507 | 4513 |
| 4517 | 4519 | 4523 | 4547 | 4549 | 4561 | 4567 | 4583 | 4591 | 4597 | 4603 | 4621 |
| 4637 | 4639 | 4643 | 4649 | 4651 | 4657 | 4663 | 4673 | 4679 | 4691 | 4703 | 4721 |
| 4723 | 4729 | 4733 | 4751 | 4759 | 4783 | 4787 | 4789 | 4793 | 4799 | 4801 | 4813 |
| 4817 | 4831 | 4861 | 4871 | 4877 | 4889 | 4903 | 4909 | 4919 | 4931 | 4933 | 4937 |
| 4943 | 4951 | 4957 | 4967 | 4969 | 4973 | 4987 | 4993 | 4999 | 5003 | 5009 | 5011 |
| 5021 | 5023 | 5039 | 5051 | 5059 | 5077 | 5081 | 5087 | 5099 | 5101 | 5107 | 5113 |
| 5119 | 5147 | 5153 | 5167 | 5171 | 5179 | 5189 | 5197 | 5209 | 5227 | 5231 | 5233 |
| 5237 | 5261 | 5273 | 5279 | 5281 | 5297 | 5303 | 5309 | 5323 | 5333 | 5347 | 5351 |
| 5381 | 5387 | 5393 | 5399 | 5407 | 5413 | 5417 | 5419 | 5431 | 5437 | 5441 | 5443 |
| 5449 | 5471 | 5477 | 5479 | 5483 | 5501 | 5503 | 5507 | 5519 | 5521 | 5527 | 5531 |
| 5557 | 5563 | 5569 | 5573 | 5581 | 5591 | 5623 | 5639 | 5641 | 5647 | 5651 | 5653 |
| 5657 | 5659 | 5669 | 5683 | 5689 | 5693 | 5701 | 5711 | 5717 | 5737 | 5741 | 5743 |
| 5749 | 5779 | 5783 | 5791 | 5801 | 5807 | 5813 | 5821 | 5827 | 5839 | 5843 | 5849 |
| 5851 | 5857 | 5861 | 5867 | 5869 | 5879 | 5881 | 5897 | 5903 | 5923 | 5927 | 5939 |
| 5953 | 5981 | 5987 | 6007 | 6011 | 6029 | 6037 | 6043 | 6047 | 6053 | 6067 | 6073 |
| 6079 | 6089 | 6091 | 6101 | 6113 | 6121 | 6131 | 6133 | 6143 | 6151 | 6163 | 6173 |
| 6197 | 6199 | 6203 | 6211 | 6217 | 6221 | 6229 | 6247 | 6257 | 6263 | 6269 | 6271 |
| 6277 | 6287 | 6299 | 6301 | 6311 | 6317 | 6323 | 6329 | 6337 | 6343 | 6353 | 6359 |
| 6361 | 6367 | 6373 | 6379 | 6389 | 6397 | 6421 | 6427 | 6449 | 6451 | 6469 | 6473 |
| 6481 | 6491 | 6521 | 6529 | 6547 | 6551 | 6553 | 6563 | 6569 | 6571 | 6577 | 6581 |
| 6599 | 6607 | 6619 | 6637 | 6653 | 6659 | 6661 | 6673 | 6679 | 6689 | 6691 | 6701 |
| 6703 | 6709 | 6719 | 6733 | 6737 | 6761 | 6763 | 6779 | 6781 | 6791 | 6793 | 6803 |
| 6823 | 6827 | 6829 | 6833 | 6841 | 6857 | 6863 | 6869 | 6871 | 6883 | 6899 | 6907 |
| 6911 | 6917 | 6947 | 6949 | 6959 | 6961 | 6967 | 6971 | 6977 | 6983 | 6991 | 6997 |
| 7001 | 7013 | 7019 | 7027 | 7039 | 7043 | 7057 | 7069 | 7079 | 7103 | 7109 | 7121 |
| 7127 | 7129 | 7151 | 7159 | 7177 | 7187 | 7193 | 7207 | 7211 | 7213 | 7219 | 7229 |
| 7237 | 7243 | 7247 | 7253 | 7283 | 7297 | 7307 | 7309 | 7321 | 7331 | 7333 | 7349 |
| 7351 | 7369 | 7393 | 7411 | 7417 | 7433 | 7451 | 7457 | 7459 | 7477 | 7481 | 7487 |
| 7489 | 7499 | 7507 | 7517 | 7523 | 7529 | 7537 | 7541 | 7547 | 7549 | 7559 | 7561 |
| 7573 | 7577 | 7583 | 7589 | 7591 | 7603 | 7607 | 7621 | 7639 | 7643 | 7649 | 7669 |
| 7673 | 7681 | 7687 | 7691 | 7699 | 7703 | 7717 | 7723 | 7727 | 7741 | 7753 | 7757 |
| 7759 | 7789 | 7793 | 7817 | 7823 | 7829 | 7841 | 7853 | 7867 | 7873 | 7877 | 7879 |
| 7883 | 7901 | 7907 | 7919 | 7927 | 7933 | 7937 | 7949 | 7951 | 7963 | 7993 | 8009 |
| 8011 | 8017 | 8039 | 8053 | 8059 | 8069 | 8081 | 8087 | 8089 | 8093 | 8101 | 8111 |
| 8117 | 8123 | 8147 | 8161 | 8167 | 8171 | 8179 | 8191 | 8209 | 8219 | 8221 | 8231 |
| 8233 | 8237 | 8243 | 8263 | 8269 | 8273 | 8287 | 8291 | 8293 | 8297 | 8311 | 8317 |
| 8329 | 8353 | 8363 | 8369 | 8377 | 8387 | 8389 | 8419 | 8423 | 8429 | 8431 | 8443 |
| 8447 | 8461 | 8467 | 8501 | 8513 | 8521 | 8527 | 8537 | 8539 | 8543 | 8563 | 8573 |
| 8581 | 8597 | 8599 | 8609 | 8623 | 8627 | 8629 | 8641 | 8647 | 8663 | 8669 | 8677 |
| 8681 | 8689 | 8693 | 8699 | 8707 | 8713 | 8719 | 8731 | 8737 | 8741 | 8747 | 8753 |
| 8761 | 8779 | 8783 | 8803 | 8807 | 8819 | 8821 | 8831 | 8837 | 8839 | 8849 | 8861 |
| 8863 | 8867 | 8887 | 8893 | 8923 | 8929 | 8933 | 8941 | 8951 | 8963 | 8969 | 8971 |
| 8999 | 9001 | 9007 | 9011 | 9013 | 9029 | 9041 | 9043 | 9049 | 9059 | 9067 | 9091 |
| 9103 | 9109 | 9127 | 9133 | 9137 | 9151 | 9157 | 9161 | 9173 | 9181 | 9187 | 9199 |
| 9203 | 9209 | 9221 | 9227 | 9239 | 9241 | 9257 | 9277 | 9281 | 9283 | 9293 | 9311 |
| 9319 | 9323 | 9337 | 9341 | 9343 | 9349 | 9371 | 9377 | 9391 | 9397 | 9403 | 9413 |
| 9419 | 9421 | 9431 | 9433 | 9437 | 9439 | 9461 | 9463 | 9467 | 9473 | 9479 | 9491 |
| 9497 | 9511 | 9521 | 9533 | 9539 | 9547 | 9551 | 9587 | 9601 | 9613 | 9619 | 9623 |
| 9629 | 9631 | 9643 | 9649 | 9661 | 9677 | 9679 | 9689 | 9697 | 9719 | 9721 | 9733 |
| 9739 | 9743 | 9749 | 9767 | 9769 | 9781 | 9787 | 9791 | 9803 | 9811 | 9817 | 9829 |
| 9833 | 9839 | 9851 | 9857 | 9859 | 9871 | 9883 | 9887 | 9901 | 9907 | 9923 | 9929 |
| 9931 | 9941 | 9949 | 9967 | 9973 | koniec płyty 🙂 ! | ||||||
Ocena artykułu:
