Bilangan Primer Tambang Ini Selalu Garis Padat

12

Mari kita buat kisi N × N spasi dan garis bawah yang dapat digunakan untuk menentukan secara visual apakah suatu bilangan prima. (N dapat berupa bilangan bulat positif.)

Grid ini memiliki tiga aturan sederhana:

  1. Kolom ke-n berisi pola berulang garis bawah n-1 diikuti oleh satu spasi. Pola ini dimulai pada baris pertama dan dihentikan, mungkin pola menengah, di baris N. (Baris dan kolom diindeks 1).
  2. Kolom pertama diganti dengan semua garis bawah, bukan semua spasi.
  3. Jika spasi terjadi di suatu tempat indeks baris sama dengan indeks kolom itu diganti dengan garis bawah.

Contoh: N = 10

           1
  1234567890 <-- column indices
 1__________
 2__________
 3__________
 4_ ________
 5__________
 6_  _______
 7__________
 8_ _ ______
 9__ _______
10_ __ _____
 ^ row indices

Indeks hanya untuk kejelasan. Grid polos itu sendiri (apa yang harus dihasilkan oleh program Anda) adalah:

__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____

Perhatikan itu:

  • Kolom pertama adalah semua garis bawah.
  • Kolom kedua adalah spasi garis bawah, ruang garis bawah, dll., Kecuali untuk garis bawah pada baris 2.
  • Kolom ketiga bertuliskan garis bawah garis bawah, garis bawah garis bawah, dll., Kecuali garis bawah pada baris 3.
  • dll.

Perhatikan juga bahwa selain 1, hanya baris bernomor prima yang memiliki garis bawah di setiap kolom.

Karena garis bawah membentang di seluruh lebar font, setiap baris bilangan prima membentuk garis solid kontinu. Jadi memeriksa apakah suatu bilangan prima atau tidak cukup mudah secara visual; cukup periksa apakah garisnya padat di semua kolom. (Kenyataannya melihat ke akar kuadrat dari indeks baris sudah cukup tetapi menghasilkan kisi itu tampak kurang elegan.)

Program

Tulis program yang akan menggambar kisi-kisi ini dengan N melalui stdin (atau alternatif terdekat). Output menuju ke stdout (atau alternatif terdekat) dan seharusnya hanya berisi spasi, garis bawah, dan baris baru, dengan baris tambahan tambahan baru.

Kode terpendek menang.

code-golf primes
sumber
Saya tidak mengerti bagaimana cara menentukan bilangan prima
Filip Bartuzi
5
@FilipBartuzi Mungkin periksa en.wikipedia.org/wiki/Sieve_of_Eratosthenes
"Kolom ke-n berisi pola berulang garis bawah n - 1 diikuti oleh satu spasi." Jadi bukankah seharusnya kolom n = 1 menjadi semua spasi, tidak semua garis bawah?
algorithmshark
6
Saya harus mengatakan saya tidak terlalu suka persyaratan "no trailing newline". Ini sangat sulit di beberapa bahasa, benar-benar mustahil dalam bahasa lain dan hanya memengaruhi program yang mencetak ke STDOUT.
Dennis
4
Deskripsi itu sulit bagi saya untuk mengerti. Ini adalah bagaimana saya akan menggambarkannya: Mulailah dengan garis N garis N garis bawah. Untuk nbaris th, buat kkarakter th spasi jika kmerupakan pembagi dari myang bukan 1 atau m.
Casey Chu

Jawaban:

7

CJam, 33 28 27 byte

q~,:)_f{f{md\1=+'_S?}0'_tN}

Cobalah online.

Bagaimana itu bekerja

q~        " Read one line from STDIN and evaluate it.                                     ";
,:)       " For “N”, push [ 1 ... N ].                                                    ";
_         " Push a copy.                                                                  ";
f{        " For each “I in [ 1 ... N ], push “I   [ 1 ... N ]”; then:                     ";
  f{      " For each “J in [ 1 ... N ], push “J   I”; then:                               ";
    md\   " Push “J % I   J / I”.                                                         ";
    1=+   " Calculate “J % I + (J / I == 1)”.                                             ";
    '_S?  " Push an underscore if the result is truthy and a space otherwise.             ";
  }       "                                                                               ";
  0'_t    " Replace the first character of the resulting array by an underscore.          ";
  N       " Push a newline.                                                               ";
}         "                                                                               ";

Contoh dijalankan

$ cjam solid-primes.cjam <<< 10
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam solid-primes.cjam <<< 100 | md5sum # trailing newline
e4396b316989813dada21141b569ccf9  -
Dennis
sumber
Saya akan memposting penjelasan ketika saya selesai bermain golf.
Dennis
9
33 byte dan Anda belum selesai bermain golf ??
5

Ruby, 77 73 karakter

puts (1..n=gets.to_i).map{|a|?_+(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join}

Beberapa trik yang saya gunakan:

  • The ..operator memiliki hampir prioritas terendah dari semua operator di Ruby, sehingga (1..n=gets.to_i)hanya bekerja.

  • Alih-alih menambahkan a!=1kondisi tambahan saat memeriksa untuk melihat apakah karakter harus berupa spasi alih-alih garis bawah (karena baris pertama adalah semua garis bawah), saya hanya memulai rentang dari 2dan menambahkan tambahan ?_.

  • Jalur A dapat menjadi jalur B:

    A | a%b==0&&a!=b ? ' ':?_
B | a!=b&&a%b==0? ' ':?_

    karena saya harus memiliki ruang ekstra di antara bdan ?di baris A, tapi itu tidak diperlukan antara 0dan ?di baris B. b?adalah metode Ruby yang valid, tetapi 0?tidak.

  • putsakan secara otomatis bergabung dengan array dengan baris baru untuk Anda, menghilangkan kebutuhan akan tambahan *"\n".

Output untuk n=100:

____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________________________________________________________________________
____________________________________________________________________________________________________
_  _________________________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ________________________________________________________________________________________________
__ _________________________________________________________________________________________________
_ __ _______________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ ______________________________________________________________________________________________
____________________________________________________________________________________________________
_ ____ _____________________________________________________________________________________________
__ _ _______________________________________________________________________________________________
_ _ ___ ____________________________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ___________________________________________________________________________________________
____________________________________________________________________________________________________
_ _  ____ __________________________________________________________________________________________
__ ___ _____________________________________________________________________________________________
_ ________ _________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ________________________________________________________________________________________
____ _______________________________________________________________________________________________
_ __________ _______________________________________________________________________________________
__ _____ ___________________________________________________________________________________________
_ _ __ ______ ______________________________________________________________________________________
____________________________________________________________________________________________________
_  _  ___ ____ _____________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ___ _______ ____________________________________________________________________________________
__ _______ _________________________________________________________________________________________
_ ______________ ___________________________________________________________________________________
____ _ _____________________________________________________________________________________________
_   _ __ __ _____ __________________________________________________________________________________
____________________________________________________________________________________________________
_ ________________ _________________________________________________________________________________
__ _________ _______________________________________________________________________________________
_ _  __ _ _________ ________________________________________________________________________________
____________________________________________________________________________________________________
_  __  ______ ______ _______________________________________________________________________________
____________________________________________________________________________________________________
_ _ ______ __________ ______________________________________________________________________________
__ _ ___ _____ _____________________________________________________________________________________
_ ____________________ _____________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ___ _______ ____________________________________________________________________________
______ _____________________________________________________________________________________________
_ __ ____ ______________ ___________________________________________________________________________
__ _____________ ___________________________________________________________________________________
_ _ ________ ____________ __________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ________ ________ _________________________________________________________________________
____ _____ _________________________________________________________________________________________
_ _ __  _____ _____________ ________________________________________________________________________
__ _______________ _________________________________________________________________________________
_ __________________________ _______________________________________________________________________
____________________________________________________________________________________________________
_     ___ _ __ ____ _________ ______________________________________________________________________
____________________________________________________________________________________________________
_ ____________________________ _____________________________________________________________________
__ ___ _ ___________ _______________________________________________________________________________
_ _ ___ _______ _______________ ____________________________________________________________________
____ _______ _______________________________________________________________________________________
_  __ ____ __________ __________ ___________________________________________________________________
____________________________________________________________________________________________________
_ _ ____________ ________________ __________________________________________________________________
__ ___________________ _____________________________________________________________________________
_ __ _ __ ___ ____________________ _________________________________________________________________
____________________________________________________________________________________________________
_   _ _  __ _____ _____ ___________ ________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________ _______________________________________________________________
__ _ _________ _________ ___________________________________________________________________________
_ _ ______________ __________________ ______________________________________________________________
______ ___ _________________________________________________________________________________________
_  __ ______ ____________ ____________ _____________________________________________________________
____________________________________________________________________________________________________
_ _  __ _ _____ ___ ___________________ ____________________________________________________________
__ _____ _________________ _________________________________________________________________________
_ ______________________________________ ___________________________________________________________
____________________________________________________________________________________________________
_   _  ____ _ ______ ______ _____________ __________________________________________________________
____ ___________ ___________________________________________________________________________________
_ ________________________________________ _________________________________________________________
__ _________________________ _______________________________________________________________________
_ _ ___ __ __________ _____________________ ________________________________________________________
____________________________________________________________________________________________________
_  _  __  ____ __ ___________ ______________ _______________________________________________________
______ _____ _______________________________________________________________________________________
_ _ __________________ ______________________ ______________________________________________________
__ ___________________________ _____________________________________________________________________
_ ____________________________________________ _____________________________________________________
____ _____________ _________________________________________________________________________________
_   _ _ ___ ___ _______ _______ _______________ ____________________________________________________
____________________________________________________________________________________________________
_ ____ ______ __________________________________ ___________________________________________________
__ _____ _ _____________________ ___________________________________________________________________
_ _  ____ _________ ____ ________________________ __________________________________________________

Sekarang termasuk Extra-Special ™ Mega-Colorful Red © Highlight-Magic ™ ® Extended Edition ©: (klik thumbnail untuk memperbesar)

Ruby dengan warna, 110 karakter

puts (1..n=gets.to_i).map{|a|x=(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join;x.index(' ')??_+x :"\e[41m_#{x}\e[0m"}

Edisi Diperpanjang

Gagang pintu
sumber
1
Sepertinya itu harus fraktal ...
Beta Decay
Hapus ruang dalam terner sebelum ' '. Ini mungkin mengacaukan stabilo sintaks Anda, tetapi masih berfungsi dengan baik. Juga,a%b<1
Nilai Tinta
*''akan bekerja sama dengan bergabung, dan Anda dapat memeriksa a<balih - alih a!=bkarena tidak ada faktor a yang lebih besar dari a. Mungkin juga ada penghematan dari mengiris string dua karakter dengan hasil dari beberapa matematika pada a dan b daripada menggunakan ternary.
histokrat
5

J - 28 char

1('_ '{~0==+&|:1&=+|/~)@:+i.

Dijelaskan oleh ledakan:

1(                    )@:+i.  NB. on vector 1..n, do
                   |/~        NB. take the table "column modulo row"
               1&=+           NB. add 1 to column 1
          =                   NB. identity matrix of size 10
            &|:               NB. transpose both tables (now table is row mod col)
           +                  NB. add them
  '_ '{~0=                    NB. space if cell=0 else underscore

Seperti apa rupanya:

   1('_ '{~0==+&|:1&=+|/~)@:+i.25
_________________________
_________________________
_________________________
_ _______________________
_________________________
_  ______________________
_________________________
_ _ _____________________
__ ______________________
_ __ ____________________
_________________________
_   _ ___________________
_________________________
_ ____ __________________
__ _ ____________________
_ _ ___ _________________
_________________________
_  __ __ ________________
_________________________
_ _  ____ _______________
__ ___ __________________
_ ________ ______________
_________________________
_   _ _ ___ _____________
____ ____________________
algoritme hiu
sumber
4

Python 2, 76 71

r=range(1,input()+1)
for i in r:print''.join("_ "[i%j<1<j<i]for j in r)

Tidak yakin apakah itu bisa mendapatkan lebih pendek dari ini ... Kata kunci ini: range, inputdan printbiaya cukup banyak.

Falko
sumber
3
Anda dapat mengganti i>j>1and i%j<1dengani>j>1>i%j
seequ
@ Sieg: Keren! Ini sebenarnya pertama kalinya saya memanfaatkan perbandingan ini.
Falko
Saya telah menulis kode karakter-untuk-karakter ini hingga nama var, termasuk i%j<1<j<i:-P. Jadi mungkin itu benar-benar tidak menjadi lebih pendek.
xnor
Sebenarnya, saya pikir (belum diuji) bisa Anda lakukan i%j<1. Ini menyiratkan i>=j.
seequ
@ Sieg: Ya, tapi kita perlu i>j, i>=juntuk tidak menghindari kekosongan pada diagonal.
Falko
3

APL (28)

'_ '[(1+(1≠⊢)∧≠∧0=|⍨)/¨⍳2⍴⎕]

Penjelasan:

  • ⍳2⍴⎕: membaca angka N dan membuat matriks koordinat N-by-N
  • (... )/¨: untuk setiap pasangan koordinat, terapkan fungsi berikut:
    • Sel harus memiliki spasi jika:
    • 0=|⍨: y modx = 0, dan
    • ≠: x tidak sama dengan y, dan
    • 1≠⊢: x tidak 1.
    • 1+: Tambahkan 1ke matriks bit yang dihasilkan karena array APL mulai dari 1.
  • '_ '[... ]: ganti masing 1- masing dengan garis bawah dan 2spasi.
marinus
sumber
Rupanya 28 adalah angka golf ajaib di sini.
2

Perl,    69   61

Versi terbaru (terima kasih, Dennis !)

$n=<>;for$i(1..$n){say"_".join"",map{$i%$_|$i==$_?_:$"}2..$n}

Versi asli:

$n=<>;for$i(1..$n){say"_".join("",map{$i%$_||$i==$_?"_":" "}(2..$n))}
Todd Lehman
sumber
1
1. Baik joinatau 2..$nkebutuhan kurung. 2. Dengan -nsakelar, Anda dapat menggunakan $_sebagai ganti $n. 3. _adalah kata pengantar yang valid, jadi tidak perlu penawaran. 4. Anda bisa menggunakannya $"sebagai ganti " ". 5. Anda bisa menggunakannya | sebagai gantinya ||.
Dennis
@Dennis - Terima kasih! Saya menerapkan beberapa dari itu. Saya tidak melakukan -nhal itu karena saya ingin menjadikannya program yang mandiri dan tidak harus mengatakannya $^N=1. Penggunaan _sebagai kata pengantar bekerja dalam kasus $i==_tetapi tidak bekerja dalam kasus $i%_karena parser pikir %_adalah hash.
Todd Lehman
1
1. Anda dapat menyimpannya sendiri dengan shebang ( #!/bin/perl -nbiasanya dihitung sebagai 1 byte), tetapi itu jelas terserah Anda. Saya tidak tahu apa yang $^N=1dilakukan ... 2. $i==_tidak akan berfungsi dengan baik; itu akan menguji apakah $i == "_". Apa yang saya maksudkan adalah menggunakan _alih-alih "_", yaitu, say _dan $i==$_?_:$".
Dennis
@ Dennis - ohhhh sial, kau benar. Hasil edit yang saya buat memperkenalkan garis diagonal melalui matriks. Malu pada saya karena tidak menangkap itu. Tetap. Saya mengerti maksud Anda _= "_"sekarang. Sayangnya, ia berfungsi dalam kasus yang terakhir tetapi memberi saya kesalahan di sebelah saykarena tampaknya berpikir itu adalah filehandle.
Todd Lehman
2

CJam, 27 byte

q~:I,{__I?'_*S+I*I<'_t}%zN*

Cobalah online.

Pendekatan ini mencapai jumlah byte yang sama dengan jawaban saya yang lain, tetapi saya pikir itu layak untuk dikirim. Alih-alih menandai kelipatan yang tepat di setiap baris, ia melakukan persis seperti yang dikatakan spesifikasi.

Bagaimana itu bekerja

q~:I                         " Read an integer I from STDIN.                              ";
    ,{                }%     " For each J ∊ {1,...,I}:                                    ";
          '_*S+              " Push J - 1 underscores followed by a space.                ";
               I*I<          " Repeat the pattern to complete I characters.               ";
       _I?                   " For the first row, replace all spaces with underscores.    ";
      _            '_t       " Replace the Jth character by an underscore.                ";
                        zN*  " Transpose rows and columns; separate with linefeeds.       ";

Contoh dijalankan

$ cjam prime-lines.cjam <<< 10; echo
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam prime-lines.cjam <<< 100 | md5sum # no trailing newline
83c7b974e1510f482322456a9dbb461f  -
Dennis
sumber
1

C, 143

C jelas bukan pilihan bahasa yang tepat untuk ini. Tetapi untuk kelengkapan, inilah salah satu cara yang mungkin untuk melakukannya dalam C. Bekerja untuk nilai n hingga 1048575. Membaca n dari input standar.

#include <stdio.h>
main(){int n,i=0,j;scanf("%d",&n);char x[1<<20];x[n+1]=0;
for(;++i<=n;){for(j=0;++j<=n;)x[j]=i%j|i==j|j==1?95:32;puts(x+1);}}

Ini sangat cepat.

  • Runtime untuk n = 1.000.000 (yang menghasilkan kisi elemen 1.000.000.000.000) adalah sekitar 55 menit pada sistem saya.

  • Runtime untuk n = 1000 (yang menghasilkan grid 1.000.000 elemen) kurang dari 1/100 detik.

Todd Lehman
sumber
4
1. Sertakan tidak diperlukan untuk beberapa kompiler (misalnya, GCC), sehingga Anda dapat menghapusnya. 2. Variabel global diinisialisasi ke 0 dan default int, sehingga Anda dapat menggunakan char x[1<<20];n,i,j;main.... 3. for(scanf("%d",&n);i++<n;)menghemat dua byte lebih scanf("%d",&n);for(;++i<=n;).
Dennis