Introducción
Los enteros de Eisenstein son números complejos de la forma
a+bω
¿Dónde a,b
están los enteros y
ω = e^(2πi/3)
Los enteros de Eisenstein forman una red triangular en el plano complejo:
Decimos que un número entero de Eisenstein z=a+bω
es primo si no puede escribirse como el producto de dos números enteros de Eisenstein no 1 (-1, -1, ω, -ω, ω ^ 2 o -ω ^ 2)
Programa
Entrada : un número natural n
.
Salida : El número de primos de Eisenstein que tienen la forma a+bω
para la que a,b
son números naturales (incluido cero) menores o iguales quen
Casos de prueba
0 → 0
1 → 0
2 → 5
3 → 9
4 → 13
5 → 20
Puntuación
Esto es code-golf
, entonces gana la menor cantidad de bytes
code-golf
primes
hexagonal-grid
complex-numbers
Mezcla Miau
fuente
fuente
a,b
pares2
solo es4
así, ¿cómo podrían5
ser primos?Respuestas:
Jalea, 24 bytes
Aproximadamente el mismo enfoque que mi respuesta de Julia.
fuente
Julia,
666260 bytesPruébalo en línea!
Explicación
Estamos interesados en los números primos en este paralelogramo en el plano complejo (ejemplo para n = 4 ):
Podemos dividirlos en números primos en las líneas verdes y en las líneas grises .
Wikipedia me dice que un número de Eisenstein z es una línea verde Eisenstein prime iff | z | es un primo natural igual a 2 mod 3.
También dice que z es una línea gris Eisenstein prima iff | z | ² = a² - ab + b² es una prima natural.
Por lo tanto, un bucle sobre un = 0 ... n y b = 0 ... n , y el cheque:
Si (a = 0 o b = 0 o a = b) y max (a, b)% 3 = 2 , cuente si max (a, b) es primo.
De lo contrario, cuente si a² - ab + b² es primo.
Sin embargo, podemos abusar de la simetría de la distribución. En lugar de contar cada línea verde una vez, ¡solo podemos contar una línea verde tres veces! Es decir, solo verifique a = 0 e incremente el contador en tres cuando encontremos una línea verde prima. Lo
a=[0;0;0:n]
logra exactamente esto.Como sabemos que solo estamos considerando la línea verde a = 0 , podemos reemplazar max (a, b) por b .
El “estado de la línea verde” está muy bien expresado en el uso de Julia Secuencia de operadores:
a<1<b%3
.(Para las líneas verdes restantes, nunca devolveremos un falso positivo: si a = b o b = 0 entonces a² - ab + b² = a² , que no puede ser primo).
Ideas
Tal vez, en lugar de escribir
a^2-a*b+b^2
, puedo reemplazar condicionalmente el exponente alb
por1
sia<1<b%3
- entonces la expresión se reduce ab
. Esto no parece ser más corto, ¡pero está ordenado!fuente
CJam (34 bytes)
Demostración en línea
fuente