Bagaimana menentukan apakah suatu bilangan prima dengan regex?

128

Saya menemukan contoh kode berikut untuk Java di RosettaCode :

public static boolean prime(int n) {
  return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
  • Saya tidak tahu Jawa khususnya tetapi mengerti semua aspek dari potongan ini kecuali untuk regex itu sendiri
  • Saya memiliki pengetahuan dasar hingga dasar-lanjutan dari Regex saat Anda menemukannya di fungsi PHP bawaan

Bagaimana .?|(..+?)\\1+cocok dengan bilangan prima?

kitlite
sumber
9
@Amir Rachum: !new String(new char[n]).matches(".?|(..+?)\\1+")setara dengan !((new String(new char[n])).matches(".?|(..+?)\\1+")).
Gumbo
14
Ini tidak hanya mahal secara komputasi tetapi juga berpotensi sangat mahal dalam memori. Jika ada yang memilih untuk menggunakan pendekatan ini, yang saya sarankan karena algoritma untuk menemukan bilangan prima sangat sederhana (mengapa di dunia menyulitkan dan membuatnya sangat boros), pemeriksaan harus dilakukan sebelum "new char [n ] "untuk memastikan itu di bawah ambang batas yang wajar. Misalnya Panggil "prime (Integer.MAX_VALUE)" dan kemudian ajukan bug ketika ia melempar OutOfMemoryError.
nicerobot
28
@nicerobot: Meringankan?
Kamera
6
@nicerobot: sebenarnya, saya mengambilnya kembali. Saya awalnya menduga sifat akademis dari pertanyaan ini menyiratkan penggunaannya hanya untuk tujuan pembelajaran, dan bahwa Anda menjadi twat yang menjengkelkan. Namun pada pemikiran kedua itu tidak terjadi; tidak pernah disebutkan atau bahkan tersirat dalam pertanyaan bahwa regex hanya untuk tujuan pembelajaran. Sebenarnya kesan pertama saya adalah bahwa ini terlihat sangat sederhana sejauh potongan kode, jadi pemula mungkin memang menganggap itu dapat digunakan dalam praktek. +1.
Kamera
7
@incrediman jangan khawatir. Saya bisa melihat bagaimana Anda berpikir seperti itu. Itu hanya niat saya untuk memperingatkan konsekuensi dari menggunakan ini, bukan untuk mencegah belajar bagaimana cara kerjanya. A sederhana "Tolong jangan menyebarkan ini." sebelum sisa komentar saya mungkin membuatnya kurang merendahkan terdengar dari perspektif awal Anda.
nicerobot

Jawaban:

120

Anda mengatakan Anda memahami bagian ini, tetapi hanya untuk menekankan, String yang dihasilkan memiliki panjang yang sama dengan jumlah yang diberikan. Jadi string memiliki tiga karakter jika dan hanya jika n == 3.

.?

Bagian pertama dari regex mengatakan, "karakter apa pun, nol atau satu kali". Jadi pada dasarnya, apakah ada nol atau satu karakter - atau, per apa yang saya sebutkan di atas n == 0 || n == 1,. Jika kami memiliki kecocokan, maka kembalikan negasi itu. Ini sesuai dengan fakta bahwa nol dan satu BUKAN prima.

(..+?)\\1+

Bagian kedua dari regex sedikit lebih rumit, bergantung pada kelompok dan referensi. Grup adalah apa saja di dalam tanda kurung, yang kemudian akan ditangkap dan disimpan oleh mesin regex untuk digunakan nanti. Referensi balik adalah grup yang cocok yang digunakan kemudian di regex yang sama.

Grup menangkap 1 karakter, lalu 1 atau lebih dari karakter apa pun. (Karakter + berarti satu atau lebih, tetapi HANYA dari karakter atau grup sebelumnya. Jadi ini bukan "dua atau empat atau enam karakter dll", melainkan "dua atau tiga dll". + Seperti +, tetapi ia mencoba untuk mencocokkan karakter sesedikit mungkin. + biasanya mencoba melahap seluruh string jika bisa, yang buruk dalam hal ini karena mencegah bagian backreference dari bekerja.)

Bagian selanjutnya adalah referensi-ulang: Kumpulan karakter yang sama (dua atau lebih), muncul lagi. Referensi balik tersebut muncul satu kali atau lebih.

Begitu. Grup yang ditangkap sesuai dengan sejumlah karakter alami (mulai 2 dan seterusnya) yang ditangkap. Kelompok yang dikatakan kemudian muncul beberapa kali alami (juga dari 2 dan seterusnya). Jika ada kecocokan, ini menyiratkan bahwa mungkin untuk menemukan produk dua angka lebih besar dari atau sama dengan 2 yang cocok dengan string panjang-n ... yang berarti Anda memiliki gabungan n. Jadi sekali lagi, kembalikan negasi dari pertandingan yang sukses: n BUKAN prima.

Jika tidak ada kecocokan yang ditemukan, maka Anda tidak dapat membuat produk Anda dari dua bilangan alami yang lebih besar dari atau sama dengan 2 ... dan Anda memiliki keduanya yang tidak cocok dan yang utama, maka dari itu kembalinya negasi dari hasil pertandingan.

Apakah kamu melihatnya sekarang? Ini luar biasa rumit (dan mahal secara komputasi!) Tetapi juga agak sederhana pada saat bersamaan, begitu Anda mendapatkannya. :-)

Saya bisa menguraikan jika Anda memiliki pertanyaan lebih lanjut, seperti tentang bagaimana sebenarnya regex parsing bekerja. Tetapi saya mencoba untuk menjaga jawaban ini tetap sederhana untuk saat ini (atau sesederhana mungkin).

Platinum Azure
sumber
10
Saya mencoba logika ini dengan JS di konsol dev chrome. di halaman web. dan baru saja melewati 5 untuk memeriksa. Halaman itu macet!
Amogh Talpallikar
Komentar di bawah ini memberikan penjelasan yang lebih baik. Silakan baca sebelum Anda melanjutkan!
Ivan Davidov
"Lebih baik" adalah subyektif - saya akan mengatakan itu mendekati masalah dari sudut yang berbeda dan merupakan pelengkap yang bagus untuk jawaban ini. :-)
Platinum Azure
1
Saya benar-benar menulis posting blog yang menjelaskan hal ini dengan lebih detail: Demystifying The Regular Expression Itu Memeriksa Jika A Number Is Prime .
Illya Gerasymchuk
73

Saya akan menjelaskan bagian regex di luar pengujian purba: regex berikut ini, diberikan String syang terdiri dari pengulangan String t, penemuan t.

    System.out.println(
        "MamamiaMamamiaMamamia".replaceAll("^(.*)\\1+$", "$1")
    ); // prints "Mamamia"

Cara kerjanya adalah bahwa menangkap regex (.*)ke \1, dan kemudian melihat apakah ada yang \1+mengikutinya. Menggunakan ^dan $memastikan bahwa kecocokan harus dari keseluruhan string.

Jadi, dengan cara tertentu, kita diberikan String s, yang merupakan "kelipatan" dari String t, dan regex akan menemukan itu t(paling lama mungkin, karena \1serakah).

Setelah Anda memahami mengapa regex ini bekerja, maka (mengabaikan alternatif pertama dalam regex OP untuk saat ini) menjelaskan bagaimana ini digunakan untuk pengujian primality sederhana.

  • Untuk menguji keutamaan n, pertama-tama hasilkan Stringpanjang n(diisi dengan yang sama char)
  • Regex menangkap Stringbeberapa panjang (katakanlah k) ke \1, dan mencoba untuk mencocokkan \1+dengan sisaString
    • Jika ada kecocokan, maka nkelipatan yang tepat k, dan karena nitu tidak prima.
    • Jika tidak ada kecocokan, maka tidak kada yang seperti itu yang membelah n, dan noleh karena itu prima

Bagaimana .?|(..+?)\1+cocok dengan bilangan prima?

Sebenarnya tidak! Ini cocok String dengan panjang yang TIDAK prima!

  • .?: Bagian pertama dari alternasi cocok Stringdengan panjang 0atau 1(BUKAN prime dengan definisi)
  • (..+?)\1+: Bagian kedua dari pergantian, variasi regex yang dijelaskan di atas, cocok Stringdengan panjang nyang merupakan "kelipatan" Stringdari panjang k >= 2(yaitu nkomposit, BUKAN prima).
    • Perhatikan bahwa pengubah enggan ?sebenarnya tidak diperlukan untuk kebenaran, tetapi dapat membantu mempercepat proses dengan mencoba lebih kecil kterlebih dahulu

Perhatikan ! booleanoperator pelengkap dalam returnpernyataan: ia meniadakan matches. Saat regex TIDAK cocok, nadalah yang utama! Ini logika ganda-negatif, jadi tidak heran itu agak membingungkan !!


Penyederhanaan

Berikut adalah penulisan ulang kode yang sederhana agar lebih mudah dibaca:

public static boolean isPrime(int n) {
    String lengthN = new String(new char[n]);
    boolean isNotPrimeN = lengthN.matches(".?|(..+?)\\1+");
    return !isNotPrimeN;
}

Di atas pada dasarnya sama dengan kode Java asli, tetapi dipecah menjadi beberapa pernyataan dengan penugasan ke variabel lokal untuk membuat logika lebih mudah dimengerti.

Kami juga dapat menyederhanakan regex, menggunakan pengulangan terbatas, sebagai berikut:

boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+");

Sekali lagi, diberi Stringpanjang n, diisi dengan yang sama char,

  • .{0,1}memeriksa apakah n = 0,1, BUKAN prima
  • (.{2,})\1+memeriksa apakah nkelipatan yang tepat k >= 2, BUKAN prima

Dengan pengecualian pengubah enggan ?aktif \1(dihilangkan untuk kejelasan), regex di atas identik dengan aslinya.


Regex lebih menyenangkan

Regex berikut menggunakan teknik serupa; itu harus mendidik:

System.out.println(
    "OhMyGod=MyMyMyOhGodOhGodOhGod"
        .replaceAll("^(.+)(.+)(.+)=(\\1|\\2|\\3)+$", "$1! $2! $3!")
); // prints "Oh! My! God!"

Lihat juga

polygenelubricants
sumber
6
+1: Saya pikir pendekatan Anda mungkin lebih baik dari saya. Tidak tahu mengapa saya mendapat begitu banyak upvotes atau tanda centang ... Anda layak mendapatkannya, saya pikir. :-( Maaf
Platinum Azure
@ Platinum: Wow, saya tidak pernah berpikir Anda akan mengatakan itu di depan umum! Terima kasih atas dukungannya. Mungkin saya akan mendapat [Populist]beberapa hari dari ini.
polygenelubricants
2
Yah, itu hanya kebenaran (seperti yang saya rasakan) ... bukan masalah besar sebenarnya. Saya di sini bukan untuk rep (meskipun itu selalu bonus dan kejutan yang menyenangkan) ... Saya di sini untuk mencoba menjawab pertanyaan ketika saya bisa. Dengan demikian seharusnya tidak mengejutkan bahwa saya dapat mengakui ketika seseorang telah melakukannya dengan lebih baik daripada yang saya miliki dalam pertanyaan tertentu.
Platinum Azure
25

Trik regex yang bagus (meskipun sangat tidak efisien) ... :)

Regex mendefinisikan non-primes sebagai berikut:

N tidak prima jika dan hanya jika N <= 1 ATAU N dapat dibagi oleh beberapa K> 1.

Alih-alih meneruskan representasi digital sederhana N ke mesin regex, ia diumpankan dengan urutan panjang N, yang terdiri dari karakter berulang. Bagian pertama dari disjunction memeriksa N = 0 atau N = 1, dan yang kedua mencari pembagi K> 1, menggunakan referensi-kembali. Ini memaksa mesin regex untuk menemukan beberapa sub-urutan yang tidak kosong yang dapat diulang setidaknya dua kali untuk membentuk urutan. Jika urutan seperti itu ada, itu berarti bahwa panjangnya membagi N, maka N tidak prima.

Eyal Schneider
sumber
2
Anehnya, bahkan setelah berulang kali membaca penjelasan yang lebih panjang dan lebih teknis, saya menemukan penjelasan ini yang membuatnya 'klik' di kepala saya.
Eight-Bit Guru
2
/^1?$|^(11+?)\1+$/

Berlaku untuk angka setelah konversi ke basis 1 (1 = 1, 2 = 11, 3 = 111, ...). Non-primes akan cocok dengan ini. Jika tidak cocok, itu prima.

Penjelasan di sini .

Dina
sumber