Tantangan ini adalah yang pertama dari serangkaian masalah operasi paling sedikit yang harus ditulis dalam GOLF CPU . Anda dapat menemukan yang berikutnya di sini
Partisi angka N
,, adalah daftar angka yang ditambahkan N
. Sebuah partisi utama adalah daftar bilangan prima yang menambahkan hingga N
.
Untuk tantangan ini, Anda diberi bilangan bulat tunggal N ≥ 2
. Anda perlu membuat partisi prime sesingkat mungkin untuk N
. Jika ada beberapa kemungkinan partisi, Anda dapat mencetak salah satunya.
Contoh:
9: [2, 7]
12: [5, 7]
95: [89, 3, 3]
337: [337]
1023749: [1023733, 13, 3]
20831531: [20831323, 197, 11]
Program Anda harus ditulis dalam GOLF CPU . Untuk input / output, Anda dapat menggunakan STDIO atau register. Daftar dapat dalam urutan apa pun, dan jika Anda menggunakan STDOUT, dapat dipisahkan dengan spasi putih atau koma (tidak perlu tanda kurung). Jelas, hardcoding solusinya tidak diperbolehkan, juga hardcoding tidak lebih dari beberapa bilangan prima pertama.
Ini adalah masalah operasi paling sedikit , jadi jawaban yang memecahkan contoh di atas dengan jumlah siklus paling sedikit menang!
sumber
Jawaban:
159.326.251 siklus
Input
n
, outputr
,s
dant
(mengabaikan nol).Testcases:
sumber
Total siklus untuk contoh: 477.918.603
Pembaruan 1: Diperbarui untuk menggunakan dugaan Lemoine .
Pembaruan 2: Diperbarui untuk menggunakan Saringan Eratosthenes alih-alih secara naif menemukan bilangan prima.
Jalankan dengan:
Contoh dijalankan:
Hitungan siklus misalnya input:
Kami menganggap
(N+1)*8
byte pertama heap, menjadi array yang berisi nilaiN+1
64-bit. (Karena tumpukan terbatas dalam ukuran, ini hanya akan berfungsi untukN < 2^57
). Nilai entri padai*8
menunjukkan apakahi
prima:Ketika kita selesai membangun array itu akan terlihat seperti
[-1, -1, 3, 5, -1, 7, -1, 11, -1, -1, -1, 13, ...]
.Kami menggunakan Saringan Eratosthenes untuk membangun array.
Selanjutnya program melakukan hal berikut dalam pseudo-code:
Ini dijamin berhasil karena dugaan Lemoine dan dugaan Goldbach yang lemah . Dugaan Lemoine belum terbukti, tetapi mungkin benar untuk angka di bawah 2 ^ 57.
sumber