Setiap bilangan prima ke-n hingga 8675309

8

Baca ini jika Anda bingung.

Tantangan:

Tujuan golf kode ini didasarkan pada nomor 8675309...

Tujuan Anda adalah untuk mencetak setiap bilangan prima dari 2 hingga 8675309, dimulai dengan angka 2 dan kemudian melewatkan 8 bilangan prima, kemudian melompati 6, kemudian melompati 7, dll. Pada dasarnya, lewati sejumlah bilangan prima yang ditentukan oleh angka berikutnya di urutannya 8675309. Bersepeda ke 8 setelah mencapai 9.

Keluaran:

2
29

(melewatkan 8 untuk sampai ke prime 10)

59

(melompati 6 untuk sampai ke prime 17)

97

(melompati 7 untuk mencapai prime 25)


Contoh: (PHP-seperti kode semu di mana $primearray berisi semua bilangan prima.)

$tn=1;
$c=1;
$na=array(8,6,7,5,3,0,9);
l:
output($prime[$tn]);
if ($prime[$tn]>=8675309) {exit(8675309)};
$c+=1;
if ($c>=8) {$c=1};
$tn+=$na[$c];
goto l;

Ketika saya mengatakan lewati 8 bilangan prima, saya bermaksud untuk beralih dari prime # 1, ke prime # 10 (melewatkan 8 di antaranya).

Setiap angka harus berada di baris baru.

Ketika Anda mencapai 0dalam 8675309, cukup cetak nomor prima berikutnya tanpa melewatkan apa pun.

Ini adalah sehingga kode terpendek (dalam-byte) menang.

gaya kaskade
sumber
2
sehingga hanya memberikan output yang tetap?
Christian Sievers
1
Anda dapat menggunakan kode dari salah satu bahasa yang digunakan untuk daftar bilangan prima di bawah sejuta tantangan, dan ubah saja 1 juta ke nomor yang Anda inginkan.
trichoplax
2
Kode pseudo Anda tampaknya masih melewati satu kurang dari yang dijelaskan, itu meningkat $c menjadi awal, dan jika kita tidak menekan 8675309 persis (kan?), Itu juga mencetak angka pertama yang melebihi nilai itu.
Christian Sievers
1
Sebagian besar tantangan memiliki hal-hal yang perlu disesuaikan sebelum siap. Untuk ide-ide tantangan di masa depan, saya menemukan kotak pasir sangat berguna untuk mendapatkan umpan balik sebelum memposting.
trichoplax
3
Aturan yang baru ditambahkan: "Baris terakhir dari output harus 8675209, terlepas dari apakah urutannya." sama sekali tidak terasa benar bagi saya, IMO tidak menambah tantangan dan hanya ada di sini untuk menyamarkan kesalahan yang telah dibuat OP dalam perhitungan awal.
zeppelin

Jawaban:

4

Mathematica 67 byte

Namun tidak mencapai 8675309 - tidak yakin dengan niat OP tentang ini.

Column@FoldList[NextPrime,2,Flatten@Array[{9,7,8,6,4,1,10}&,12937]]
martin
sumber
1
Akan menang jika tidak menggunakan built-in untuk bilangan prima ...
DepressedDaniel
7
ini adalah mathatica yang sedang kita bicarakan - kita beruntung tidak ada builtin untuk ini
Zwei
3

Bertanya-tanya , 47 byte

P\tk582161P;(_>@(os tk1P;P\dp +1#0P))cyc8675309

Ya ampun, ini semakin lambat seiring berjalannya waktu ...

Penjelasan

P\tk582161P;

Mengambil 582161 (jumlah bilangan prima <= 8675309) item dari daftar bilangan prima tak terbatas Pdan mendeklarasikan ulang hasilnya sebagai P.

(_>@(...))cyc8675309

Secara tak terbatas siklus digit 8675309 dan melakukan takewhile pada daftar yang dihasilkan.

os tk1P;P\dp +1#0P

Keluarkan item pertama dalam P, drop cycle item + 1elemen dari P, dan hasil ulang menyatakan sebagai P. Operasi ini Pjuga bertindak sebagai nilai kebenaran untuk sementara; jika daftar itu kosong / palsu (artinya kita telah mencapai 8675309), maka kita berhenti mengambil dari daftar bersepeda.

Implementasi lebih cepat (untuk pengujian)

P\tk582161P;(_>@(os tk1P;P\dp +1#0P;#0))cyc8675309

Masih sangat lambat, tetapi terasa lebih cepat.

Mama Fun Roll
sumber
3

Jelly , 23 29 24 byte

+6 byte untuk tambalan sementara untuk memenuhi persyaratan untuk mencetak 8675309.
-5 byte pindah ke pegolf tetapi pendekatan yang lebih lambat untuk mengatasinya.

“⁹Ṁ:’©D‘ẋ“2Ṿ’R®ÆR¤ṁḢ€;®Y

Sekarang terlalu lambat untuk dijalankan di TryItOnline, tetapi berjalan secara lokal dalam beberapa menit, menghasilkan angka-angka yang ditunjukkan di bawah ini dengan umpan baris di antara (# bilangan prima dilewati yang ditunjukkan di bawah dalam tanda kurung):

2, 29, 59, 97, 127, 149, 151, 199, 257, 293, 349, 383, 409, 419, ...
 (8) (6) (7) (5)  (3)  (0)  (9)  (8)  (6)  (7)  (5)  (3)  (0)

..., 8674537, 8674727, 8674867, 8675003, 8675053, 8675113, 8675137, 8675309
            (8)      (6)      (7)      (5)      (3)      (0)      (4)*

* yang terakhir hanya lompatan efektif 4, karena hanya ditambahkan ke daftar.

Klik di sini untuk versi menggunakan 3659 bukannya 8675309, yang memiliki 19 set empat lompatan (daripada 12937 set 7) dan tambahkan 3659 (yang merupakan lompatan efektif 6).

Bagaimana?

“⁹Ṁ:’©D‘ẋ“2Ṿ’R®ÆR¤ṁḢ€;®Y - Main link: no arguments
“⁹Ṁ:’                    - base 250 number: 8675309
     ©                   - save in register
      D                  - convert to a decimal list: [8, 6, 7, 5, 3, 0, 9]
       ‘                 - increment: [9,7,8,6,4,1,10]
         “2Ṿ’            - base 250 number: 12937
        ẋ                - repeat: [9,7,8,6,4,1,10,9,7,8,6,4,1,10, ... ,9,7,8,6,4,1,10]
             R           - range (vectorises) [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7], ...]
                 ¤       - nilad followed by link(s) as a nilad
              ®          - retrieve value from register: 8675309
               ÆR        - prime range [2,3,5,7, ... ,8675309]
                  ṁ      - mould the primes like the range list:
                               [[2,3,5,7,11,13,17,19,23],[29,31,37,41,43,47,53],...]
                   Ḣ€    - head €ach: [2,29,59,97,127,149,151,199, ..., 8675137]
                      ®  - retrieve value from register: 8675309
                     ;   - concatenate: [2,29,59,97,127,149,151,199, ..., 8675137, 8675309]
                       Y - join with line feeds
                         - implicit print
Jonathan Allan
sumber
Program harus mencetak 8675309 di akhir, seperti kode pseudo.
gaya cascading
1
@ cascading-style OK, saya tidak menyadari dari spesifikasi yang merupakan persyaratan (saya harus melihat kode semu Anda!). Saya telah memperbaikinya dengan cara yang naif untuk saat ini dan akan melihat kemungkinan mengubah metode di beberapa titik untuk mengurangi ini dalam ukuran.
Jonathan Allan
2

Ruby, 121 byte

Mengejar baris baru di akhir file yang tidak perlu dan tidak disimpan.

P=[]
(2..8675309).map{|c|s=1;P.map{|p|s*=c%p};P<<c if s!=0}
S=[9,7,8,6,4,1,10]*P[-1]
while y=P[0]
p y
P.shift S.shift
end

Penjelasan: Padalah array bilangan prima. cadalah kandidat utama; sadalah produk residu modulo setiap perdana yang lebih kecil; jika ada residu seperti itu nol (menunjukkan ckomposit), smenjadi (dan tetap) nol.

Generator bilangan prima lambat. Ini akan membutuhkan waktu lama untuk dijalankan. Pengujian dilakukan dengan mengganti Parray yang dihasilkan dengan cara yang lebih efisien (khususnya, hubung singkat pada divisi genap, dan juga banyak membantu untuk menghentikan pengujian pada akar kuadrat).

DepresiDaniel
sumber
2

Haskell, 122 byte

Ini mungkin yang diminta:

s(a:b)=a:s[c|c<-b,c`mod`a>0]
f(a:b)(s:t)=a:f(drop s b)t
main=mapM print$takeWhile(<8675310)$f(s[2..])$cycle[8,6,7,5,3,0,9]

Saya bisa menghemat beberapa byte dengan menghitung berapa jumlah yang dibutuhkan, dan mengganti takeWhiledengan take. Itu juga akan memungkinkan untuk beradaptasi dengan keputusan apa pun tentang angka terakhir yang akan dikeluarkan. Ini sudah mencetak angka hingga 600000 menggunakan sangat sedikit memori dalam pengujian saya, jadi saya pikir itu bisa berjalan sepanjang jalan.

Sievers Kristen
sumber
-1 Tidak bekerja: rextester.com/GPCX98454
cascading-style
3
Mungkinkah mereka memiliki batasan runtime? Ini berfungsi di sana jika Anda menggantinya 8675310dengan 8675, katakanlah. Dan itu berfungsi untuk saya (dikompilasi, dengan optimasi, tidak mencoba tanpa) dalam bentuk aslinya. Mesin yang lebih cepat, mulai lebih awal dari tes pertama, telah mencapai 1.600.000.
Christian Sievers
1
Mendapatkan ruang stack meluap. Sekarang coba dengan yang lebih besar. Atau, dapat menggunakan generator utama yang lebih naif yang mengarah ke ukuran kode yang sama.
Christian Sievers
2

Haskell, 109 byte

(p:z)%(x:r)=print p>>(drop x z)%r
p%x=pure()
[n|n<-[2..8675309],all((>0).mod n)[2..n-1]]%cycle[8,6,7,5,3,0,9]

Cobalah online! (terpotong 8675309ke 8675, jika tidak habis pada Coba online )

Pemakaian:

* Utama> [n | n0) .mod n) [2..n-1]]% cycle [8,6,7,5,3,0,9]
2
29
59
97
127
149
151
199
257
293
349
383
409
419
467
541
587
631
661
691
701
769
829
881
941
983
1013
...
Laikoni
sumber
2

Perl 6 ,  65 73  67 byte

$_=8675309;.[0].put for (2..$_).grep(*.is-prime).rotor(1 X+.comb)

(gagal mencetak 8675137 karena hilang :partial)

$_=8675309;.[0].put for ^$_ .grep(*.is-prime).rotor((1 X+.comb),:partial)
$_=8675309;.[0].put for ^($_+33) .grep(*.is-prime).rotor(1 X+.comb)

Dengan menggeser ujung Range, :partialdapat dihapus.

Cobalah (batas 5 detik ditambahkan) Lihat selesai

Contoh awal dihitung waktunya pada 52 menit 41,464 detik.

Diperluas:

$_ = 8675309;

  .[0]              # get the first value out of inner list
  .put              # print with trailing newline

for                 # for every one of the following

  ^($_+33)          # the Range ( add 33 so that 「.rotor」 doesn't need 「:partial」 )
  .grep(*.is-prime) # the primes
  .rotor(
    1 X+ .comb      # (1 X+ (8,6,7,5,3,0,9)) eqv (9,7,8,6,4,1,10)
  )

Hasil dari rotorpanggilan adalah urutan berikut

(
 (  2   3   5   7  11  13  17  19  23)     #  9 (8)
 ( 29  31  37  41  43  47  53)             #  7 (6)
 ( 59  61  67  71  73  79  83  89)         #  8 (7)
 ( 97 101 103 107 109 113)                 #  6 (5)
 (127 131 137 139)                         #  4 (3)
 (149)                                     #  1 (0)
 (151 157 163 167 173 179 181 191 193 197) # 10 (9)

 (199 211 223 227 229 233 239 241 251)     #  9 (8)
 (257 263 269 271 277 281 283)             #  7 (6)
 (293 307 311 313 317 331 337 347)         #  8 (7)
 (349 353 359 367 373 379)                 #  6 (5)
 (383 389 397 401)                         #  4 (3)
 (409)                                     #  1 (0)
 (419 421 431 433 439 443 449 457 461 463) # 10 (9)

 ...
)
Brad Gilbert b2gills
sumber
Jawaban yang bagus, berapa lama untuk menyelesaikannya?
gaya cascading
1
@ cascading-style Butuh waktu hampir 53 menit untuk menyelesaikannya. Untung aku membiarkannya selesai, karena saya lupa :partialkata keterangan pada panggilan untuk.rotor
Brad Gilbert b2gills
1

Befunge, 136 byte

p2>:1>1+:"~"%55p:"~"/45p:*\`!v
1+^<+ 1<_:#!v#%+g55@#*"~"g54:_\:!#v_1-\
p00%7+1: ,+64g00.:_^#!`***"'(CS":$<^0-"/"g4
>5g#*^#"~"g5<
8675309

Cobalah online! , tapi ketahuilah bahwa ini akan habis waktu lama sebelum mencapai akhir. Versi kompilasi pada mesin lokal saya selesai dalam waktu kurang dari 10 detik.

Penjelasan

Untuk menguji primality, kita mengulangi rentang 2 hingga sqrt ( n ) dan memeriksa apakah n adalah kelipatan dari salah satu dari nilai-nilai tersebut - jika tidak, itu prima. Proses ini diperumit oleh fakta bahwa nilai yang diulang perlu disimpan dalam "variabel" sementara, dan karena sel memori Befunge terbatas dalam ukuran, penyimpanan itu harus dipecah menjadi dua sel. Untuk menangani bilangan prima yang dilewati, kami menggunakan "tabel" pencarian (yang dapat Anda lihat pada baris 5) untuk melacak rentang berbeda yang perlu dilewati.

Saya tidak akan melakukan analisis rinci kode, karena ada cukup banyak kode interleaving dengan perintah yang dibagi di jalur kode yang berbeda untuk menghemat ruang. Ini membuat hal-hal agak sulit untuk diikuti dan saya tidak berpikir itu akan sangat menarik bagi siapa pun yang belum terbiasa dengan Befunge.

Output Sampel

2
29
59
97
127
149
151
199
...
8674397
8674537
8674727
8674867
8675003
8675053
8675113
8675137
James Holderness
sumber
1

Bash (+ coreutils), 98, 94 byte

EDIT:

  • Filter baris yang dioptimalkan sedikit, -4 byte

Golf

seq 8675309|factor|grep -oP "^.*(?=: \S*$)"|sed 1b\;`printf '%d~45b;' {10,17,25,31,35,36,46}`d

Uji

>seq 8675309|factor|grep -oP "^.*(?=: \S*$)"|sed 1b\;`printf '%d~45b;' {10,17,25,31,35,36,46}`d| head -25
2
29
59
97
127
149
151
199
257
293
349
383
409
419
467
541
587
631
661
691
701
769
829
881
941

Cobalah secara Online! (terbatas pada N <1000, untuk membuatnya berjalan cepat)

Versi lengkap membutuhkan sekitar ~ 15 detik untuk selesai di mesin saya.

zeppelin
sumber
Saya ingin tahu siapa yang memasukkan "faktor" dalam coreutils.
Jasen
1
@Jasen lihat unix.stackexchange.com/a/58105/182018
zeppelin