¿Es casi perfecto?
Salvadera
Definición: Un número entero positivo nes casi primo , si se puede escribir en la forma n=p^kdonde pes primo y ktambién números enteros positivos. En otras palabras, la factorización prima de ncontiene solo el mismo número.
Entrada: un entero positivo2<=n<=2^31-1
Salida: un valor verdadero, si nes casi primo , y un valor falso, si no.
Casos de prueba veraces:
2
3
4
8
9
16
25
27
32
49
64
81
1331
2401
4913
6859
279841
531441
1173481
7890481
40353607
7528289
Casos de prueba de falsedad
6
12
36
54
1938
5814
175560
9999999
17294403
No utilice las lagunas legales estándar. Esto es código de golf, ¡ así que gana la respuesta más corta en bytes!
Respuestas
Sagemath , 2 bytes
GF
Salidas por excepción .
¡Pruébelo en línea!
La orden interna Sagemath \$\text{GF}\$crea un campo de orden de Galois \$n\$. Sin embargo, recuerda que \$\mathbb{F}_n\$es solo un campo si \$n = p^k\$donde \$p\$es primo y \$k\$un número entero positivo. Por tanto, la función lanza una excepción si y solo si su entrada no es una potencia principal.
Python 2 , 42 bytes
f=lambda n,p=2:n%p and f(n,p+1)or p**n%n<1
¡Pruébelo en línea!
Dado que Python no tiene incorporados para los números primos, nos conformamos con verificar la divisibilidad.
Encontramos el primo más pequeño pque es un factor de ncontando hacia arriba p=2,3,4,...hasta que nsea divisible por p, es n%pdecir, cero. Allí, comprobamos que este pes el único factor primo comprobando que una potencia alta de pes divisible por n. Para esto, es p**nsuficiente.
Como programa:
43 bytes
n=input()
p=2
while n%p:p+=1
print p**n%n<1
¡Pruébelo en línea!
Esto podría ser más corto con códigos de salida si están permitidos.
46 bytes
lambda n:all(n%p for p in range(2,n)if p**n%n)
¡Pruébelo en línea!
Lenguaje de programación Shakespeare , 329 bytes
,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]
Ajax:Listen tothy.
Page:You cat.
Scene V:.
Page:You is the sum ofYou a cat.
Is the remainder of the quotient betweenI you nicer zero?If soLet usScene V.
Scene X:.
Page:You is the cube ofYou.Is you worse I?If soLet usScene X.
You is the remainder of the quotient betweenYou I.Open heart
¡Pruébelo en línea!
Emite 0si la entrada es casi prima y un entero positivo en caso contrario. No estoy seguro de que sea un resultado aceptable; cambiarlo costaría unos pocos bytes.
Explicación:
- Escena I:
Pagetoma entrada (llame a eston). InicializarAjax = 1. - Escena V: Incremento
Ajaxhasta queAjaxes un divisor dePage; llamar al valor finalpEsto da el divisor más pequeño dePage, que está garantizado como primo. - Escena X: Cubo
Ajaxhasta que termine con un poder dep, digamosp^kcuál es mayor quen. Entoncesnes casi primo iffndividep^k.
MATL , 4 bytes
Yf&=
- Para casi primos, la salida es una matriz que contiene solo
1s, que es veraz . - De lo contrario, la salida es una matriz que contiene varios
1sy al menos uno0, que es falso .
¡Pruébelo en línea! O verifique todos los casos de prueba , incluida la prueba de veracidad / falsedad.
Cómo funciona
% Implicit input
Yf % Prime factors. Gives a vector with the possibly repeated prime factors
&= % Matrix of all pair-wise equality comparisons
% Implicit output
R , 36 32 29 bytes
-3 bytes al generar un vector de valores booleanos sin extraer el primer elemento
!(a=2:(n=scan()))[!n%%a]^n%%n
¡Pruébelo en línea!
Genera un vector de valores booleanos. En R, un vector de valores booleanos es verdadero si el primer elemento es TRUE.
Primero, encuentra el divisor más pequeño pde n. Podemos hacer esto comprobando todos los números enteros (no solo los números primos), ya que el divisor más pequeño de un número entero (aparte de 1) es siempre un número primo. Aquí, asean todos los números enteros entre 2y n, luego p=a[!n%%a][1]es el primer elemento del aque se divide n.
Entonces nes casi primo si se ndivide p^n.
Esto falla para cualquier entrada moderadamente grande, por lo que aquí está la versión anterior que funciona para la mayoría de las entradas más grandes:
R , 36 33 bytes
!log(n<-scan(),(a=2:n)[!n%%a])%%1
¡Pruébelo en línea!
Calcule el logaritmo de nen base p: este es un entero sif nes casi primo.
Esto fallará debido a la inexactitud del punto flotante para ciertas (pero lejos de todas) entradas grandes, en particular para un caso de prueba: \$4913=17^3\$.
C (gcc) , 43 bytes
f(n,i){for(i=1;n%++i;);n=i<n&&f(n/i)^i?:i;}
¡Pruébelo en línea!
Devuelve psi nes casi primo y 1si no.
f(n,i){
for(i=1;n%++i;); // identify i = the least prime factor of n
n=i<n&&f(n/i)^i // if n is neither prime nor almost-prime
? // return 1
:i; // return i
}
Wolfram Language (Mathematica) , 11 bytes
PrimePowerQ
¡Pruébelo en línea!
@Sisyphus guardó 1 byte
05AB1E , 2 bytes
ÒË
¡Pruébelo en línea!
Comentó:
Ò -- Are all the primes in the prime decomposition
Ë -- Equal?
J , 9 8 bytes
1=#@=@q:
¡Pruébelo en línea!
-1 byte gracias a xash
Comprueba si la autoclasificación = de los factores primos q:tiene una longitud #igual a uno1=
APL (Dyalog Classic) , 33 31 26 bytes
{⍵∊∊(((⊢~∘.×⍨)1↓⍳)⍵)∘*¨⍳⍵}
-5 bytes de la sugerencia de Kevin Cruijssen.
Advertencia: muy, muy lento para números más grandes.
Explicación
{⍵∊∊(((⊢~∘.×⍨)1↓⍳)⍵)∘*¨⍳⍵} ⍵=n in all the following steps
⍳⍵ range from 1 to n
∘*¨ distribute power operator across left and right args
(((⊢~∘.×⍨)1↓⍳)⍵) list of primes till n
∊ flatten the right arg(monadic ∊)
⍵∊ is n present in the primes^(1..n)?
¡Pruébelo en línea!
Pyth , 5 bytes
!t{PQ
¡Pruébelo en línea!
Explicación:
Q - Takes integer input
P - List of prime factors
{ - Remove duplicate elements
t - Removes first element
! - Would return True if remaining list is empty, otherwise False
Setanta , 61 59 bytes
gniomh(n){p:=2nuair-a n%p p+=1nuair-a n>1 n/=p toradh n==1}
Pruébalo aquí
Notas:
- La palabra clave adecuada es
gníomh, pero Setanta permite deletrearla sin los acentos, así que lo hice para recortar un byte.
Haskell , 36 bytes
f n=mod(until((<1).mod n)(+1)2^n)n<1
¡Pruébelo en línea!
36 bytes
f n=and[mod(gcd d n^n)n<2|d<-[1..n]]
¡Pruébelo en línea!
39 bytes
f n=all((`elem`[1,n]).gcd n.(^n))[2..n]
¡Pruébelo en línea!
39 bytes
f n=mod n(n-sum[1|1<-gcd n<$>[1..n]])<1
¡Pruébelo en línea!
40 bytes
f n=and[mod(p^n)n<1|p<-[2..n],mod n p<1]
¡Pruébelo en línea!
JavaScript (ES6), 43 bytes
Sin BigInts
Devuelve un valor booleano.
f=(n,k=1)=>n%1?!~~n:f(n<0?n/k:n%++k?n:-n,k)
¡Pruébelo en línea!
Una función recursiva que primero busca el divisor más pequeño \$k>1\$de \$n\$y luego divide \$-n\$por \$k\$hasta que ya no sea un número entero. (La única razón por la que invertimos el signo de \$n\$cuando \$k\$ se encuentra es distinguir entre los dos pasos del algoritmo.)
Si \$n\$es casi primo, el resultado final es \$-\dfrac{1}{k}>-1\$. Entonces terminamos con \$\lceil n\rceil=0\$.
Si \$n\$no es casi primo, existe un \$q>k\$coprime con \$k\$tal que \$n=q\times k^{m}\$. En ese caso, el resultado final es \$-\dfrac{q}{k}<-1\$. Entonces terminamos con \$\lceil n\rceil<0\$.
JavaScript (ES11), 33 bytes
Con BigInts
Con BigInts, usar el enfoque de @ xnor es probablemente el camino más corto a seguir.
Devuelve un valor booleano.
f=(n,k=1n)=>n%++k?f(n,k):k**n%n<1
¡Pruébelo en línea!
Retina 0.8.2 , 50 bytes
.+
$* ^(?=(11+?)\1*$)((?=\1+$)(?=(1+)(\3+)$)\4)+1$
¡Pruébelo en línea! Link incluye casos de prueba más rápidos. Basado en la respuesta de @ Deadcode a Match strings cuya longitud es una cuarta potencia . Explicación:
.+
$*
Convierta la entrada en unario.
^(?=(11+?)\1*$)
Comience por hacer coincidir el factor más pequeño \ $ p \ $ de \ $ n \ $ . ( \ $ p \ $ es necesariamente primo, por supuesto).
(?=\1+$)(?=(1+)(\3+)$)
Mientras \ $ p | \ frac n {p ^ i} \ $ , encuentre el factor propio más grande de \ $ \ frac n {p ^ i} \ $ , que es necesariamente \ $ \ frac n {p ^ {i + 1}} \ $ .
\4
La factorización también captura \ $ (p - 1) \ frac n {p ^ {i + 1}} \ $ , que se resta de \ $ \ frac n {p ^ i} \ $ , dejando \ $ \ frac n { p ^ {i + 1}} \ $ para la siguiente pasada por el bucle.
(...)+1$
Repite la división por \$ p \$tantas veces como sea posible, luego verifique que \$ \frac n { p^k } = 1 \$.
Io , 48 bytes
Puerto de la respuesta R de @ RobinRyder.
method(i,c :=2;while(i%c>0,c=c+1);i log(c)%1==0)
¡Pruébelo en línea!
Explicación
method(i, // Take an input
c := 2 // Set counter to 2
while(i%c>0, // While the input doesn't divide counter:
c=c+1 // Increment counter
)
i log(c)%1==0 // Is the decimal part of input log counter equal to 0?
)
Ensamblado (MIPS, SPIM) , 238 bytes, 6 * 23 = 138 bytes ensamblados
main:li$v0,5 syscall move$t3,$v0 li$a0,0
li$t2,2 w:bgt$t2,$t3,d div$t3,$t2 mfhi$t0
bnez$t0,e add$a0,$a0,1 s:div$t3,$t2 mfhi$t0
bnez$t0,e div$t3,$t3,$t2
b s
e:add$t2,$t2,1
b w
d:move$t0,$a0
li$a0,0 bne$t0,1,p
add$a0,$a0,1
p:li$v0,1
syscall
¡Pruébelo en línea!
Brachylog , 2 bytes
¿Son todos los factores primos iguales?
ḋ=
¡Pruébelo en línea!
GAP 4.7, 31 bytes
n->Length(Set(FactorsInt(n)))<2
Esta es una lambda. Por ejemplo, la declaración
Filtered([2..81], n->Length(Set(FactorsInt(n)))<2 );
produce la lista [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81 ].
¡Pruébelo en línea!
MathGolf , 10 bytes
╒g¶mÉk╒#─╧
Port of @Razetime 's APL (Dyalog Classic) responde , ¡así que asegúrate de votarlo también!
Pruébelo en línea.
Explicación:
╒ # Push a list in the range [1, (implicit) input-integer)
g # Filter it by:
¶ # Check if it's a prime
m # Map each prime to,
É # using the following three operations:
k╒ # Push a list in the range [1, input-integer) again
# # Take the current prime to the power of each value in this list
─ # After the map, flatten the list of lists
╧ # And check if this list contains the (implicit) input-integer
# (after which the entire stack joined together is output implicitly)
Factor , 35 bytes
: f ( n -- ? ) factors all-equal? ;
¡Pruébelo en línea!
Japonés , 6 bytes
Siento que esto debería ser 1 o 2 bytes más corto ...
k ä¶ ×
Pruébelo : incluye todos los casos de prueba
Java, 69 (o 64?) Bytes
n->{int c=0,t=1;for(;t++<n;)if(n%t<1)for(c++;n%t<1;)n/=t;return c<2;}
Pruébelo en línea.
Explicación:
n->{ // Method with integer parameter and boolean return-type
int c=0, // Counter-integer, starting at 0
t=1;for(;t++<n;) // Loop `t` in the range (1,n]:
if(n%t<1) // If the input is divisible by `t`:
for(c++; // Increase the counter by 1
n%t<1;) // Loop as long as the input is still divisible by `t`
n/=t; // And divide `n` by `t` every iteration
return c<2;} // Return whether the counter is 1
Si se nos permitiera ignorar las inexactitudes del punto flotante, un puerto de la respuesta R de @ RobinRyder sería 64 bytes en su lugar:
n->{int m=1;for(;n%++m>0;);return Math.log(n)/Math.log(m)%1==0;}
Pruébelo en línea.
Explicación:
n->{ // Method with integer parameter and boolean return-type
int m=1; // Minimum divisor integer `m`, starting at 1
for(;n%++m>0;); // Increase `m` by 1 before every iteration with `++m`
// And continue looping until the input is divisible by `m`
return Math.log(n)/Math.log(m)
// Calculate log_m(n)
%1==0;} // And return whether it has no decimal values after the comma
Pero, desafortunadamente, este enfoque falla para el caso de prueba 4913que se convertiría en 2.9999999999999996lugar de 3.0debido a inexactitudes de punto flotante (tiene éxito para todos los demás casos de prueba).
Una posible solución sería de 71 bytes :
n->{int m=1;for(;n%++m>0;);return(Math.log(n)/Math.log(m)+1e9)%1<1e-8;}
Pruébelo en línea.
Gelatina , 3 bytes
ÆfE
¡Pruébelo en línea!
Burlesque , 6 bytes
rifCsm
¡Pruébelo en línea!
Explicación:
ri # Read integer from input
fC # Find its prime factorisation
sm # Are all values the same?