È quasi primo?
Sandbox
Definizione: un numero intero positivo nè quasi primo , se può essere scritto nella forma in n=p^kcui pè un numero primo ed kè anche un numero intero positivo. In altre parole, la scomposizione in fattori primi di ncontiene solo lo stesso numero.
Input: un numero intero positivo2<=n<=2^31-1
Output: un valore vero, se nè quasi primo , e un valore falso, se no.
Casi di test veritieri:
2
3
4
8
9
16
25
27
32
49
64
81
1331
2401
4913
6859
279841
531441
1173481
7890481
40353607
7528289
Casi di test di falsità
6
12
36
54
1938
5814
175560
9999999
17294403
Si prega di non utilizzare scappatoie standard. Questo è il golf in codice, quindi la risposta più breve in byte vince!
Risposte
Sagemath , 2 byte
GF
Uscite tramite eccezione .
Provalo online!
Il Sagemath builtin \$\text{GF}\$crea un campo d'ordine Galois \$n\$. Tuttavia, ricorda che \$\mathbb{F}_n\$è solo un campo se \$n = p^k\$dove \$p\$è un numero primo e \$k\$un numero intero positivo. Quindi la funzione genera un'eccezione se e solo se il suo input non è una potenza principale.
Python 2 , 42 byte
f=lambda n,p=2:n%p and f(n,p+1)or p**n%n<1
Provalo online!
Poiché Python non ha alcun built-in per i numeri primi, ci accontentiamo di controllare la divisibilità.
Troviamo il numero primo più piccolo di pcui è un fattore ncontando fino a p=2,3,4,...quando nè divisibile per p, cioè n%pzero. Lì, controlliamo che questo psia l'unico fattore primo controllando che un'elevata potenza di psia divisibile per n. Per questo, p**nbasta.
Come programma:
43 byte
n=input()
p=2
while n%p:p+=1
print p**n%n<1
Provalo online!
Questo potrebbe essere più breve con i codici di uscita, se consentiti.
46 byte
lambda n:all(n%p for p in range(2,n)if p**n%n)
Provalo online!
Linguaggio di programmazione Shakespeare , 329 byte
,.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
Provalo online!
Emette 0se l'ingresso è quasi primo e un numero intero positivo in caso contrario. Non sono sicuro che questo sia un output accettabile; cambiarlo costerebbe pochi byte.
Spiegazione:
- Scena I:
Pagericeve un input (chiamalon). InizializzaAjax = 1. - Scena V: Incremento
Ajaxfino a quandoAjaxè un divisore diPage; chiama il valore finalepQuesto dà il più piccolo divisore diPage, che è garantito essere un numero primo. - Scena X: cubo
Ajaxfinché non si finisce con un potere dip, diciamop^kche è maggiore din. Alloranè quasi primo se e solo sendividep^k.
MATL , 4 byte
Yf&=
- Per i quasi primi l'output è una matrice contenente solo
1s, il che è vero . - Altrimenti l'output è una matrice contenente diversi se
1almeno uno0, che è falso .
Provalo online! Oppure verifica tutti i casi di test , inclusi i test di veridicità / falsità.
Come funziona
% 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 byte
-3 byte emettendo un vettore di booleani senza estrarre il primo elemento
!(a=2:(n=scan()))[!n%%a]^n%%n
Provalo online!
Restituisce un vettore di valori booleani. In R, un vettore di booleani è vero se e solo se il primo elemento lo è TRUE.
Innanzitutto, trova il più piccolo divisore pdi n. Possiamo farlo controllando tutti i numeri interi (non solo i primi), poiché il più piccolo divisore di un intero (a parte 1) è sempre un numero primo. Qui, lasciate aessere tutti gli interi compresi tra 2e n, quindi p=a[!n%%a][1]è il primo elemento di acui divide n.
Allora nè quasi primo se e solo se ndivide p^n.
Questo non riesce per qualsiasi input moderatamente grande, quindi ecco la versione precedente che funziona per gli input più grandi:
R , 36 33 byte
!log(n<-scan(),(a=2:n)[!n%%a])%%1
Provalo online!
Calcola il logaritmo di nin base p: questo è un numero intero se ne solo se è primo.
Questo fallirà a causa di imprecisione in virgola mobile per alcuni (ma tutt'altro che tutti) input di grandi dimensioni, in particolare per un caso di test: \$4913=17^3\$.
C (gcc) , 43 byte
f(n,i){for(i=1;n%++i;);n=i<n&&f(n/i)^i?:i;}
Provalo online!
Restituisce pse nè quasi primo e 1altrimenti.
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 byte
PrimePowerQ
Provalo online!
@Sisyphus ha salvato 1 byte
05AB1E , 2 byte
ÒË
Provalo online!
Commentato:
Ò -- Are all the primes in the prime decomposition
Ë -- Equal?
J , 9 8 byte
1=#@=@q:
Provalo online!
-1 byte grazie a xash
Verifica se l' autoclassificazione = dei fattori primi q:ha lunghezza #pari a uno1=
APL (Dyalog Classic) , 33 31 26 byte
{⍵∊∊(((⊢~∘.×⍨)1↓⍳)⍵)∘*¨⍳⍵}
-5 byte dal suggerimento di Kevin Cruijssen.
Avvertenza: molto, molto lento per numeri più grandi.
Spiegazione
{⍵∊∊(((⊢~∘.×⍨)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)?
Provalo online!
Pyth , 5 byte
!t{PQ
Provalo online!
Spiegazione:
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 byte
gniomh(n){p:=2nuair-a n%p p+=1nuair-a n>1 n/=p toradh n==1}
Provalo qui
Appunti:
- La parola chiave corretta è
gníomh, ma Setanta consente di scriverla senza gli accenti, quindi l'ho fatto per radere un byte.
Haskell , 36 byte
f n=mod(until((<1).mod n)(+1)2^n)n<1
Provalo online!
36 byte
f n=and[mod(gcd d n^n)n<2|d<-[1..n]]
Provalo online!
39 byte
f n=all((`elem`[1,n]).gcd n.(^n))[2..n]
Provalo online!
39 byte
f n=mod n(n-sum[1|1<-gcd n<$>[1..n]])<1
Provalo online!
40 byte
f n=and[mod(p^n)n<1|p<-[2..n],mod n p<1]
Provalo online!
JavaScript (ES6), 43 byte
Senza BigInts
Restituisce un valore booleano.
f=(n,k=1)=>n%1?!~~n:f(n<0?n/k:n%++k?n:-n,k)
Provalo online!
Una funzione ricorsiva che cerca prima il divisore più piccolo \$k>1\$di \$n\$e poi divide \$-n\$di \$k\$finché non è più un numero intero. (L'unico motivo per cui invertiamo il segno di \$n\$quando \$k\$ si trova per distinguere tra i due passaggi dell'algoritmo.)
Se \$n\$è quasi primo, il risultato finale è \$-\dfrac{1}{k}>-1\$. Quindi finiamo con \$\lceil n\rceil=0\$.
Se \$n\$non è quasi primo, esistono alcuni \$q>k\$coprimo con \$k\$tale che \$n=q\times k^{m}\$. In tal caso, il risultato finale è \$-\dfrac{q}{k}<-1\$. Quindi finiamo con \$\lceil n\rceil<0\$.
JavaScript (ES11), 33 byte
Con BigInts
Con BigInts, l'utilizzo dell'approccio di @ xnor è probabilmente la strada più breve da percorrere.
Restituisce un valore booleano.
f=(n,k=1n)=>n%++k?f(n,k):k**n%n<1
Provalo online!
Retina 0.8.2 , 50 byte
.+
$* ^(?=(11+?)\1*$)((?=\1+$)(?=(1+)(\3+)$)\4)+1$
Provalo online! Il collegamento include casi di test più rapidi. Basato sulla risposta di @ Deadcode a Match stringhe la cui lunghezza è una quarta potenza . Spiegazione:
.+
$*
Converti l'input in unario.
^(?=(11+?)\1*$)
Inizia facendo corrispondere il fattore più piccolo \ $ p \ $ di \ $ n \ $ . ( \ $ p \ $ è necessariamente primo, ovviamente.)
(?=\1+$)(?=(1+)(\3+)$)
Mentre \ $ p | \ frac n {p ^ i} \ $ , trova il fattore proprio più grande di \ $ \ frac n {p ^ i} \ $ , che è necessariamente \ $ \ frac n {p ^ {i + 1}} \ $ .
\4
La scomposizione in fattori cattura anche \ $ (p - 1) \ frac n {p ^ {i + 1}} \ $ , che viene sottratto da \ $ \ frac n {p ^ i} \ $ , lasciando \ $ \ frac n { p ^ {i + 1}} \ $ per il passaggio successivo del ciclo.
(...)+1$
Ripeti la divisione per \$ p \$quante più volte possibile, quindi controlla che \$ \frac n { p^k } = 1 \$.
Io , 48 byte
Risposta di Port of @ RobinRyder.
method(i,c :=2;while(i%c>0,c=c+1);i log(c)%1==0)
Provalo online!
Spiegazione
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?
)
Assembly (MIPS, SPIM) , 238 byte, 6 * 23 = 138 byte assemblati
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
Provalo online!
Brachylog , 2 byte
Tutti i fattori primi sono uguali?
ḋ=
Provalo online!
GAP 4.7, 31 byte
n->Length(Set(FactorsInt(n)))<2
Questa è una lambda. Ad esempio, la dichiarazione
Filtered([2..81], n->Length(Set(FactorsInt(n)))<2 );
restituisce l'elenco [ 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 ].
Provalo online!
MathGolf , 10 byte
╒g¶mÉk╒#─╧
Port of @Razetime 's APL (Dyalog Classic) risposta , quindi assicurati di votare anche lui!
Provalo online.
Spiegazione:
╒ # 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)
Fattore , 35 byte
: f ( n -- ? ) factors all-equal? ;
Provalo online!
Japt , 6 byte
Mi sento come se questo dovesse essere 1 o 2 byte più corto ...
k ä¶ ×
Provalo : include tutti i casi di test
Java, 69 (o 64?) Byte
n->{int c=0,t=1;for(;t++<n;)if(n%t<1)for(c++;n%t<1;)n/=t;return c<2;}
Provalo online.
Spiegazione:
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
Se potessimo ignorare le imprecisioni in virgola mobile, una porta della risposta R di @ RobinRyder sarebbe invece di 64 byte :
n->{int m=1;for(;n%++m>0;);return Math.log(n)/Math.log(m)%1==0;}
Provalo online.
Spiegazione:
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
Ma sfortunatamente questo approccio fallisce per il caso di test 4913che diventerebbe 2.9999999999999996invece che a 3.0causa di imprecisioni in virgola mobile (ha successo per tutti gli altri casi di test).
Una potenziale correzione sarebbe 71 byte :
n->{int m=1;for(;n%++m>0;);return(Math.log(n)/Math.log(m)+1e9)%1<1e-8;}
Provalo online.
Gelatina , 3 byte
ÆfE
Provalo online!
Burlesque , 6 byte
rifCsm
Provalo online!
Spiegazione:
ri # Read integer from input
fC # Find its prime factorisation
sm # Are all values the same?