pengantar
Bilangan bulat Eisenstein adalah bilangan kompleks dari bentuk itu
a+bω
Di mana a,b
bilangan bulat, dan
ω = e^(2πi/3)
Bilangan bulat Eisenstein membentuk kisi segitiga di bidang kompleks:
Kami mengatakan bahwa bilangan bulat Eisenstein z=a+bω
adalah bilangan prima jika tidak dapat ditulis sebagai produk dari dua non-unit (bukan 1, -1, ω, -ω, ω ^ 2, atau -ω ^ 2) bilangan bulat Eisenstein
Program
Input : Nomor alami n
.
Output : Jumlah bilangan prima Eisenstein yang dari bentuk a+bω
yang a,b
merupakan bilangan (termasuk nol) kurang dari atau sama dengann
Uji Kasus
0 → 0
1 → 0
2 → 5
3 → 9
4 → 13
5 → 20
Mencetak gol
Ini code-golf
, jumlah byte yang paling sedikit menang
code-golf
primes
hexagonal-grid
complex-numbers
Meow Mix
sumber
sumber
a,b
pasangan2
hanya4
jadi bagaimana mungkin5
mereka menjadi prima?Jawaban:
Jelly, 24 byte
Pendekatan yang hampir sama dengan jawaban Julia saya.
sumber
Julia,
666260 byteCobalah online!
Penjelasan
Kami tertarik pada bilangan prima dalam jajaran genjang ini pada bidang kompleks (contoh untuk n = 4 ):
Kita dapat membaginya menjadi bilangan prima pada garis hijau , dan pada garis abu - abu .
Wikipedia memberi tahu saya nomor Eisenstein z adalah garis hijau Eisenstein prime iff | z | adalah prime natural sama dengan 2 mod 3.
Ia juga mengatakan z adalah garis abu - abu Eisenstein prime iff | z | ² = a² - ab + b² adalah prime natural.
Jadi kita mengulang a = 0 ... n dan b = 0 ... n , dan periksa:
Jika (a = 0 atau b = 0 atau a = b) dan maks (a, b)% 3 = 2 , maka hitung apakah maks (a, b) adalah bilangan prima.
Jika tidak, hitung apakah a² - ab + b² adalah bilangan prima.
Namun, kami dapat menyalahgunakan simetri distribusi. Alih-alih menghitung setiap garis hijau satu kali, kita bisa menghitung satu garis hijau tiga kali! Yaitu, hanya memeriksa a = 0 dan menambah penghitung dengan tiga ketika kita menemukan prime garis hijau. The
a=[0;0;0:n]
mencapai persis ini.Karena kita tahu kita hanya mempertimbangkan garis hijau a = 0 , kita dapat mengganti maks (a, b) dengan b .
“Kondisi jalur hijau” adalah baik dinyatakan dalam Julia menggunakan chaining Operator:
a<1<b%3
.(Untuk garis hijau yang tersisa, kami tidak akan pernah mengembalikan false positive: jika a = b atau b = 0 maka a² - ab + b² = a² , yang tidak dapat menjadi prima.)
Ide ide
Mungkin, alih-alih menulis
a^2-a*b+b^2
, saya bisa kondisional menggantikan eksponen dib
oleh1
saata<1<b%3
- maka ekspresi mengurangi keb
. Ini sepertinya tidak lebih pendek, tetapi rapi!sumber
CJam (34 byte)
Demo online
sumber