rumah » Untuk penuh » Aturan bilangan prima. Bilangan bukan prima

Aturan bilangan prima. Bilangan bukan prima

bilangan prima adalah bilangan asli (bilangan bulat positif) yang habis dibagi tanpa sisa hanya oleh dua bilangan asli: oleh dan oleh dirinya sendiri. Dengan kata lain, bilangan prima mempunyai tepat dua pembagi alami: dan bilangan itu sendiri.

Menurut definisinya, himpunan semua pembagi suatu bilangan prima adalah dua unsur, yaitu. mewakili satu set.

Himpunan semua bilangan prima dilambangkan dengan simbol. Jadi, berdasarkan definisi himpunan bilangan prima, kita dapat menulis: .

Urutan bilangan prima terlihat seperti ini:

Teorema Dasar Aritmatika

Teorema Dasar Aritmatika menyatakan bahwa setiap bilangan asli yang lebih besar dari satu dapat direpresentasikan sebagai hasil kali bilangan prima, dan dengan cara yang unik, hingga orde faktornya. Jadi, bilangan prima adalah "bahan penyusun" dasar himpunan bilangan asli.

Ekspansi bilangan asli title="Diberikan oleh QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} resmi:

di mana bilangan prima, dan . Misalnya, perluasan kanonik bilangan asli terlihat seperti ini: .

Menyatakan bilangan asli sebagai hasil kali bilangan prima disebut juga faktorisasi suatu bilangan.

Sifat-sifat Bilangan Prima

Saringan Eratosthenes

Salah satu algoritma yang paling terkenal untuk mencari dan mengenali bilangan prima adalah saringan Eratosthenes. Jadi algoritma ini dinamai ahli matematika Yunani Eratosthenes dari Cyrene, yang dianggap sebagai penulis algoritma tersebut.

Untuk mencari semua bilangan prima yang kurang dari suatu bilangan tertentu, ikuti metode Eratosthenes, ikuti langkah-langkah berikut:

Langkah 1. Tuliskan semua bilangan asli dari dua sampai , mis. .
Langkah 2. Tetapkan nilai pada variabel, yaitu nilai yang sama dengan bilangan prima terkecil.
Langkah 3. Coret dalam daftar semua bilangan dari sampai yang merupakan kelipatan , yaitu bilangan: .
Langkah 4. Temukan bilangan pertama yang tidak disilangkan dalam daftar yang lebih besar dari , dan tetapkan nilai bilangan ini ke variabel.
Langkah 5. Ulangi langkah 3 dan 4 hingga nomor tercapai.

Proses penerapan algoritma akan terlihat seperti ini:

Semua bilangan tak bersilangan yang tersisa dalam daftar pada akhir proses penerapan algoritma akan menjadi himpunan bilangan prima dari sampai .

Dugaan Goldbach

Sampul buku “Paman Petros dan Hipotesis Goldbach”

Terlepas dari kenyataan bahwa bilangan prima telah dipelajari oleh ahli matematika sejak lama, banyak masalah terkait yang masih belum terpecahkan hingga saat ini. Salah satu masalah paling terkenal yang belum terpecahkan adalah hipotesis Goldbach, yang dirumuskan sebagai berikut:

Benarkah setiap bilangan genap yang lebih besar dari dua dapat dinyatakan sebagai jumlah dua bilangan prima (hipotesis biner Goldbach)?
Benarkah setiap bilangan ganjil yang lebih besar dari 5 dapat dinyatakan sebagai suatu penjumlahan? tiga sederhana angka (hipotesis Goldbach terner)?

Harus dikatakan bahwa hipotesis terner Goldbach adalah kasus khusus dari hipotesis biner Goldbach, atau seperti yang dikatakan ahli matematika, hipotesis terner Goldbach lebih lemah daripada hipotesis biner Goldbach.

Dugaan Goldbach menjadi dikenal luas di luar komunitas matematika pada tahun 2000 berkat aksi pemasaran promosional yang dilakukan oleh perusahaan penerbitan Bloomsbury USA (AS) dan Faber and Faber (UK). Penerbit-penerbit ini, setelah menerbitkan buku “Paman Petros dan Dugaan Goldbach,” berjanji akan memberikan hadiah sebesar 1 juta dolar AS kepada siapa pun yang membuktikan hipotesis Goldbach dalam waktu 2 tahun sejak tanggal penerbitan buku tersebut. Terkadang hadiah dari penerbit yang disebutkan di atas dikacaukan dengan hadiah untuk memecahkan Masalah Hadiah Milenium. Jangan salah, hipotesis Goldbach tidak diklasifikasikan oleh Clay Institute sebagai “tantangan milenium”, meskipun hal ini berkaitan erat dengan Hipotesis Riemann- salah satu “tantangan milenium”.

Buku “Bilangan prima. Jalan panjang menuju ketidakterbatasan"

Sampul buku “Dunia Matematika. bilangan prima. Jalan panjang menuju ketidakterbatasan"

Selain itu, saya merekomendasikan membaca buku sains populer yang menarik, yang penjelasannya berbunyi: “Pencarian bilangan prima adalah salah satu masalah paling paradoks dalam matematika. Para ilmuwan telah mencoba memecahkannya selama beberapa milenium, namun seiring dengan berkembangnya versi dan hipotesis baru, misteri ini masih belum terpecahkan. Kemunculan bilangan prima tidak tunduk pada sistem apa pun: bilangan tersebut muncul secara spontan dalam rangkaian bilangan asli, mengabaikan semua upaya ahli matematika untuk mengidentifikasi pola dalam barisannya. Buku ini akan memungkinkan pembaca menelusuri evolusi konsep ilmiah dari zaman kuno hingga saat ini dan memperkenalkan teori paling menarik dalam pencarian bilangan prima.”

Selain itu, saya akan mengutip bagian awal bab kedua buku ini: “Bilangan prima adalah salah satu topik penting yang membawa kita kembali ke awal mula matematika, dan kemudian, di sepanjang jalur yang semakin kompleks, membawa kita ke garis depan. ilmu pengetahuan modern. Oleh karena itu, akan sangat berguna untuk mengikuti hal-hal menarik dan sejarah yang kompleks teori bilangan prima: bagaimana tepatnya perkembangannya, bagaimana sebenarnya fakta dan kebenaran yang saat ini dianggap diterima secara umum dikumpulkan. Dalam bab ini kita akan melihat bagaimana generasi matematikawan mempelajari bilangan asli dengan cermat untuk mencari aturan yang memprediksi munculnya bilangan prima - aturan yang menjadi semakin sulit dipahami seiring dengan kemajuan pencarian. Kita juga akan melihat secara rinci konteks sejarah: kondisi di mana para ahli matematika bekerja dan sejauh mana pekerjaan mereka melibatkan praktik mistis dan semi-religius, yang sangat berbeda dari metode ilmiah yang digunakan di zaman kita. Namun demikian, perlahan dan dengan susah payah, landasan dipersiapkan untuk pandangan baru yang menginspirasi Fermat dan Euler pada abad ke-17 dan ke-18.”

Jawaban Ilya benar, tapi tidak terlalu detail. Omong-omong, pada abad ke-18, satu masih dianggap sebagai bilangan prima. Misalnya saja ahli matematika hebat seperti Euler dan Goldbach. Goldbach adalah penulis salah satu dari tujuh masalah milenium - hipotesis Goldbach. Rumusan aslinya menyatakan bahwa setiap bilangan genap dapat direpresentasikan sebagai jumlah dua bilangan prima. Selain itu, awalnya 1 diperhitungkan sebagai bilangan prima, dan kita melihat ini: 2 = 1+1. Ini adalah contoh terkecil yang memenuhi rumusan awal hipotesis. Nanti dikoreksi, dan susunan kata-katanya menjadi tampilan modern: “setiap bilangan genap, dimulai dengan 4, dapat dinyatakan sebagai jumlah dari dua bilangan prima.”

Mari kita ingat definisinya. Bilangan prima adalah bilangan asli p yang hanya memiliki 2 pembagi alami yang berbeda: p itu sendiri dan 1. Akibat wajar dari definisi: bilangan prima p hanya memiliki satu pembagi prima - p itu sendiri.

Sekarang anggap saja 1 adalah bilangan prima. Menurut definisinya, bilangan prima hanya mempunyai satu pembagi prima, yaitu bilangan prima itu sendiri. Ternyata bilangan prima apa pun yang lebih besar dari 1 habis dibagi oleh bilangan prima yang berbeda dengannya (1). Tetapi dua bilangan prima yang berbeda tidak dapat dibagi satu sama lain, karena jika tidak, bilangan tersebut bukanlah bilangan prima, melainkan bilangan komposit, dan ini bertentangan dengan definisinya. Dengan pendekatan ini, ternyata hanya ada 1 bilangan prima – satuannya sendiri. Tapi ini tidak masuk akal. Oleh karena itu, 1 bukanlah bilangan prima.

1, dan juga 0, membentuk kelas bilangan lain - kelas elemen netral terhadap operasi n-ary di beberapa subset bidang aljabar. Selain itu, sehubungan dengan operasi penjumlahan, 1 juga merupakan elemen pembangkit ring bilangan bulat.

Dengan pertimbangan ini, tidak sulit untuk menemukan analogi bilangan prima pada struktur aljabar lainnya. Misalkan kita mempunyai grup perkalian yang dibentuk dari pangkat 2, dimulai dari 1: 2, 4, 8, 16, ... dst. 2 bertindak sebagai elemen formatif di sini. Bilangan prima dalam golongan ini adalah bilangan yang lebih besar dari unsur terkecilnya dan hanya habis dibagi oleh bilangan itu sendiri dan unsur terkecilnya. Di grup kami, hanya 4 yang memiliki sifat seperti itu. Tidak ada lagi bilangan prima di grup kami.

Jika 2 juga merupakan bilangan prima dalam kelompok kita, lihat paragraf pertama - sekali lagi ternyata hanya 2 yang merupakan bilangan prima.

Bilangan prima adalah bilangan asli yang hanya habis dibagi oleh dirinya sendiri dan oleh satu.

Bilangan sisanya disebut bilangan komposit.

Bilangan asli prima

Namun tidak semua bilangan asli adalah bilangan prima.

Bilangan asli prima hanyalah bilangan yang hanya habis dibagi oleh dirinya sendiri dan oleh satu.

Contoh bilangan prima:

2; 3; 5; 7; 11; 13;...

bilangan bulat prima

Oleh karena itu, hanya bilangan asli yang merupakan bilangan prima.

Artinya, bilangan prima adalah bilangan asli.

Tapi semua bilangan asli juga bilangan bulat.

Jadi, semua bilangan prima adalah bilangan bulat.

Contoh bilangan prima:

2; 3; 5; 7; 11; 13; 17; 19; 23;...

Bahkan bilangan prima

Hanya ada satu bilangan prima genap, yaitu bilangan dua.

Semua bilangan prima lainnya ganjil.

Mengapa bilangan genap yang lebih besar dari dua tidak bisa menjadi bilangan prima?

Tetapi karena bilangan genap yang lebih besar dari dua akan habis dibagi oleh dirinya sendiri, bukan oleh satu dan oleh dua, maka bilangan tersebut akan selalu mempunyai tiga pembagi, dan mungkin lebih.

Semua bilangan asli, kecuali satu, terbagi menjadi bilangan prima dan komposit. Bilangan prima adalah bilangan asli yang hanya mempunyai dua pembagi: satu dan bilangan itu sendiri. Semua yang lain disebut komposit. Sifat-sifat bilangan prima dipelajari oleh cabang khusus matematika - teori bilangan. Dalam teori ring, bilangan prima berkaitan dengan unsur-unsur yang tidak dapat direduksi.

Berikut barisan bilangan prima yang dimulai dari 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, ... dst.

Menurut teorema dasar aritmatika, setiap bilangan asli yang lebih besar dari satu dapat dinyatakan sebagai hasil kali bilangan prima. Pada saat yang sama, ini adalah satu-satunya cara untuk merepresentasikan bilangan asli hingga urutan faktornya. Berdasarkan hal tersebut, kita dapat mengatakan bahwa bilangan prima adalah bagian dasar dari bilangan asli.

Representasi bilangan asli ini disebut penguraian bilangan asli menjadi bilangan prima atau faktorisasi suatu bilangan.

Salah satu yang paling kuno dan cara yang efektif Perhitungan bilangan prima adalah “saringan Erasstophenes”.

Praktek telah menunjukkan bahwa setelah menghitung bilangan prima menggunakan saringan Erastophenes, perlu untuk memeriksa apakah nomor yang diberikan sederhana. Untuk tujuan ini, tes khusus telah dikembangkan, yang disebut tes kesederhanaan. Algoritme pengujian ini bersifat probabilistik. Mereka paling sering digunakan dalam kriptografi.

Omong-omong, untuk beberapa kelas angka terdapat tes primalitas khusus yang efektif. Misalnya untuk memeriksa primalitas bilangan Mersenne digunakan uji Luc-Lehmer, dan untuk memeriksa primalitas bilangan Fermat digunakan uji Pepin.

Kita semua tahu bahwa jumlahnya tak terhingga banyaknya. Pertanyaan yang tepat muncul: ada berapa bilangan prima? Ada juga bilangan prima yang jumlahnya tak terhingga. Bukti paling kuno dari proposisi ini adalah bukti Euclid, yang dituangkan dalam Elemen. Bukti Euclid terlihat seperti ini:

Bayangkan banyaknya bilangan prima berhingga. Mari kalikan dan tambahkan satu. Bilangan yang dihasilkan tidak dapat dibagi dengan himpunan bilangan prima berhingga mana pun, karena sisa pembagian dengan himpunan bilangan prima tersebut menghasilkan satu. Jadi, bilangan tersebut harus habis dibagi oleh suatu bilangan prima yang tidak termasuk dalam himpunan ini.

Teorema distribusi bilangan prima menyatakan bahwa banyaknya bilangan prima yang kurang dari n, dilambangkan dengan π(n), bertambah sebagai n / ln(n).

Setelah ribuan tahun mempelajari bilangan prima, bilangan prima terbesar yang diketahui adalah 243112609 − 1. Bilangan ini memiliki 12.978.189 angka desimal dan merupakan bilangan prima Mersenne (M43112609). Penemuan ini dilakukan pada tanggal 23 Agustus 2008 di Fakultas Matematika Universitas uCLA sebagai bagian dari pencarian terdistribusi untuk proyek GIMPS bilangan prima Mersenne.

Rumah ciri khas Bilangan Mersenne adalah adanya uji primalitas Luc-Lemaire yang sangat efektif. Dengan bantuannya, bilangan prima Mersenne, dalam jangka waktu yang lama, merupakan bilangan prima terbesar yang diketahui.

Namun hingga saat ini, banyak pertanyaan mengenai bilangan prima yang belum mendapat jawaban pasti. Pada Kongres Internasional Matematika ke-5, Edmund Landau merumuskan permasalahan pokok dalam bidang bilangan prima:

Masalah Goldbach atau masalah Landau yang pertama adalah perlu dibuktikan atau disangkal bahwa setiap bilangan genap yang lebih besar dari 2 dapat dinyatakan sebagai jumlah dua bilangan prima, dan setiap bilangan ganjil yang lebih besar dari 5 dapat dinyatakan sebagai jumlah tiga bilangan prima.
Masalah kedua Landau memerlukan jawaban atas pertanyaan: apakah himpunan " kembar sederhana» - bilangan prima yang selisihnya 2?
Dugaan Legendre atau permasalahan ketiga Landau adalah: benarkah antara n2 dan (n+1)2 selalu ada bilangan prima?
Masalah keempat Landau: apakah himpunan bilangan prima berbentuk n2 + 1 tak terhingga?
Selain soal di atas, ada soal menentukan bilangan prima yang tak terhingga pada banyak barisan bilangan bulat seperti bilangan Fibonacci, bilangan Fermat, dan lain-lain.

Artikel ini membahas tentang konsep bilangan prima dan bilangan komposit. Definisi angka-angka tersebut diberikan dengan contoh. Kami memberikan bukti bahwa jumlah bilangan prima tidak terbatas dan kami akan mencatatnya dalam tabel bilangan prima menggunakan metode Eratosthenes. Pembuktian akan diberikan untuk menentukan apakah suatu bilangan prima atau komposit.

Yandex.RTB RA-339285-1

Bilangan Prima dan Komposit – Pengertian dan Contohnya

Bilangan prima dan bilangan komposit diklasifikasikan sebagai bilangan bulat positif. Mereka harus lebih besar dari satu. Pembagi juga dibagi menjadi sederhana dan komposit. Untuk memahami konsep bilangan komposit, Anda harus mempelajari terlebih dahulu konsep pembagi dan kelipatannya.

Definisi 1

Bilangan prima adalah bilangan bulat yang lebih besar dari satu dan mempunyai dua pembagi positif, yaitu bilangan itu sendiri dan 1.

Definisi 2

Bilangan komposit adalah bilangan bulat yang lebih besar dari satu dan mempunyai paling sedikit tiga pembagi positif.

Satu bukanlah bilangan prima atau bilangan komposit. Bilangan ini hanya mempunyai satu pembagi positif, sehingga berbeda dengan bilangan positif lainnya. Semua bilangan bulat positif disebut bilangan asli, yaitu digunakan dalam penghitungan.

Definisi 3

bilangan prima adalah bilangan asli yang hanya mempunyai dua pembagi positif.

Definisi 4

Angka komposit adalah bilangan asli yang mempunyai lebih dari dua pembagi positif.

Bilangan apa pun yang lebih besar dari 1 adalah bilangan prima atau komposit. Dari sifat habis dibagi kita mengetahui bahwa 1 dan bilangan a akan selalu menjadi pembagi bagi sembarang bilangan a, yaitu habis dibagi oleh dirinya sendiri dan oleh 1. Mari kita berikan definisi bilangan bulat.

Definisi 5

Bilangan asli yang bukan bilangan prima disebut bilangan komposit.

Bilangan prima: 2, 3, 11, 17, 131, 523. Mereka hanya habis dibagi oleh dirinya sendiri dan 1. Bilangan komposit: 6, 63, 121, 6697. Artinya, bilangan 6 dapat diuraikan menjadi 2 dan 3, dan 63 menjadi 1, 3, 7, 9, 21, 63, dan 121 menjadi 11, 11, sehingga pembaginya adalah 1, 11, 121. Angka 6697 diurai menjadi 37 dan 181. Perhatikan bahwa konsep bilangan prima dan bilangan koprima merupakan konsep yang berbeda.

Untuk mempermudah penggunaan bilangan prima, Anda perlu menggunakan tabel:

Tabel untuk semua bilangan asli yang ada tidak realistis, karena jumlahnya tak terhingga. Ketika jumlahnya mencapai ukuran 10.000 atau 10.00000000, maka Anda harus mempertimbangkan untuk menggunakan Saringan Eratosthenes.

Mari kita perhatikan teorema yang menjelaskan pernyataan terakhir.

Teorema 1

Pembagi positif terkecil selain 1 dari suatu bilangan asli yang lebih besar dari satu disebut bilangan prima.

Bukti 1

Misalkan a adalah bilangan asli yang lebih besar dari 1, b adalah pembagi bukan satu terkecil dari a. B adalah bilangan prima perlu dibuktikan dengan menggunakan metode kontradiksi.

Misalkan b adalah bilangan komposit. Dari sini kita mengetahui bahwa ada pembagi untuk b, yang berbeda dari 1 dan juga dari b. Pembagi seperti itu dilambangkan sebagai b 1. Hal ini diperlukan kondisi 1< b 1 < b telah selesai.

Dari kondisi tersebut jelas a habis dibagi b, b habis dibagi b 1, artinya konsep habis dibagi dinyatakan sebagai berikut: a = bq dan b = b 1 · q 1 , dari mana a = b 1 · (q 1 · q) , di mana q dan pertanyaan 1 adalah bilangan bulat. Menurut aturan perkalian bilangan bulat, kita mendapatkan hasil kali bilangan bulat adalah bilangan bulat dengan persamaan bentuk a = b 1 · (q 1 · q) . Dapat dilihat bahwa b 1 adalah pembagi bilangan a. Ketimpangan 1< b 1 < b Bukan bersesuaian, karena kita menemukan bahwa b adalah pembagi positif terkecil dan bukan-1 dari a.

Teorema 2

Ada bilangan prima yang jumlahnya tak terhingga.

Bukti 2

Agaknya kita mengambil sejumlah bilangan asli n yang terbatas dan menyatakannya sebagai p 1, p 2, …, p n. Mari kita pertimbangkan opsi untuk menemukan bilangan prima yang berbeda dari yang ditunjukkan.

Mari kita perhatikan bilangan p yang sama dengan p 1, p 2, ..., p n + 1. Tidak sama dengan masing-masing bilangan yang bersesuaian dengan bilangan prima berbentuk p 1, p 2, ..., p n. Bilangan p adalah bilangan prima. Maka teorema tersebut dianggap terbukti. Jika komposit, maka perlu mengambil notasi p n + 1 dan tunjukkan bahwa pembaginya tidak berimpit dengan salah satu p 1, p 2, ..., p n.

Jika tidak demikian, maka berdasarkan sifat dapat dibagi produk p 1, p 2, ..., p n , kita temukan bahwa itu habis dibagi pn + 1. Perhatikan bahwa ekspresi p n + 1 membagi bilangan p sama dengan jumlah p 1, p 2, ..., p n + 1. Kami memperoleh ekspresi p n + 1 Suku kedua dari jumlah ini, yaitu 1, harus dibagi, tetapi hal ini tidak mungkin.

Dapat dilihat bahwa bilangan prima apa pun dapat ditemukan di antara bilangan prima mana pun. Oleh karena itu, ada banyak bilangan prima yang tak terhingga.

Karena bilangan prima banyak sekali, maka tabelnya dibatasi pada bilangan 100, 1000, 10000, dan seterusnya.

Saat menyusun tabel bilangan prima, Anda harus memperhitungkan bahwa tugas seperti itu memerlukan pemeriksaan bilangan secara berurutan, mulai dari 2 hingga 100. Jika tidak ada pembagi, maka dicatat dalam tabel, jika komposit maka tidak dimasukkan ke dalam tabel.

Mari kita lihat langkah demi langkah.

Jika diawali dengan angka 2, maka angka tersebut hanya memiliki 2 pembagi: 2 dan 1, artinya dapat dimasukkan ke dalam tabel. Sama dengan nomor 3. Angka 4 itu komposit, harus diurai menjadi 2 dan 2. Angka 5 adalah bilangan prima yang artinya dapat dicatat dalam tabel. Lakukan ini sampai angka 100.

Metode ini tidak nyaman dan lama. Anda dapat membuat tabel, tetapi Anda harus mengeluarkan uang sejumlah besar waktu. Perlu menggunakan kriteria keterbagian yang akan mempercepat proses pencarian pembagi.

Cara menggunakan saringan Eratosthenes dianggap paling nyaman. Mari kita lihat tabel di bawah ini sebagai contoh. Pertama-tama dituliskan angka 2, 3, 4, ..., 50.

Sekarang Anda perlu mencoret semua angka yang merupakan kelipatan 2. Lakukan coretan berurutan. Kami mendapatkan tabel seperti:

Kita lanjutkan dengan mencoret bilangan yang merupakan kelipatan 5. Kita mendapatkan:

Coretlah bilangan-bilangan yang merupakan kelipatan 7, 11. Pada akhirnya tabelnya terlihat seperti itu

Mari kita beralih ke rumusan teorema.

Teorema 3

Pembagi positif dan non-1 terkecil dari bilangan dasar a tidak melebihi a, dimana a adalah akar aritmatika nomor tertentu.

Bukti 3

B perlu dinotasikan sebagai pembagi terkecil dari suatu bilangan komposit a. Ada bilangan bulat q, dimana a = b · q, dan kita mendapatkan b ≤ q. Ketimpangan bentuk tidak bisa diterima b > q, karena syaratnya dilanggar. Kedua ruas pertidaksamaan b ≤ q harus dikalikan dengan sembarang nomor positif b tidak sama dengan 1. Kita peroleh bahwa b · b ≤ b · q, di mana b 2 ≤ a dan b ≤ a.

Dari teorema yang terbukti jelas bahwa mencoret bilangan pada tabel berarti harus memulai dengan bilangan yang sama dengan b 2 dan memenuhi pertidaksamaan b 2 ≤ a. Artinya, jika bilangan yang kelipatan 2 dicoret, maka prosesnya dimulai dari 4, dan kelipatan 3 dengan 9, begitu seterusnya hingga 100.

Menyusun tabel seperti itu menggunakan teorema Eratosthenes menunjukkan bahwa ketika semua bilangan komposit dicoret, akan tetap ada bilangan prima yang tidak melebihi n. Pada contoh di mana n = 50, kita mendapatkan n = 50. Dari sini kita mendapatkan bahwa saringan Eratosthenes menyaring semua bilangan komposit yang nilainya tidak lebih besar dari nilai akar 50. Pencarian nomor dilakukan dengan cara mencoret.

Sebelum menyelesaikannya, Anda perlu mencari tahu apakah bilangan tersebut prima atau komposit. Kriteria keterbagian sering digunakan. Mari kita lihat pada contoh di bawah ini.

Contoh 1

Buktikan bahwa bilangan 898989898989898989 merupakan bilangan komposit.

Larutan

Jumlah angka-angka suatu bilangan adalah 9 8 + 9 9 = 9 17. Artinya bilangan 9 · 17 habis dibagi 9, berdasarkan uji habis dibagi 9. Oleh karena itu, ini adalah komposit.

Tanda-tanda seperti itu tidak mampu membuktikan keutamaan suatu bilangan. Jika verifikasi diperlukan, tindakan lain harus diambil. Cara yang paling cocok adalah dengan menyebutkan angka-angka. Selama proses tersebut, bilangan prima dan bilangan komposit dapat ditemukan. Artinya, angkanya tidak boleh melebihi nilai a. Artinya, bilangan a harus didekomposisi menjadi faktor utama. jika terpenuhi, maka bilangan a dapat dianggap bilangan prima.

Contoh 2

Tentukan bilangan komposit atau bilangan prima 11723.

Larutan

Sekarang Anda perlu mencari semua pembagi untuk bilangan 11723. Perlu mengevaluasi 11723 .

Dari sini kita melihat bahwa 11723< 200 , то 200 2 = 40 000 , dan 11.723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

Untuk perkiraan angka 11723 yang lebih akurat, Anda perlu menulis ekspresi 108 2 = 11 664, dan 109 2 = 11 881 , Itu 108 2 < 11 723 < 109 2 . Oleh karena itu 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

Ketika diperluas, kita menemukan bahwa 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 semuanya bilangan prima. Semua proses ini dapat digambarkan sebagai pembagian dengan kolom. Artinya, bagi 11723 dengan 19. Angka 19 adalah salah satu faktornya, karena kita mendapatkan pembagian tanpa sisa. Mari kita nyatakan pembagian sebagai kolom: