Est-ce presque parfait?

Question

bac à sable

Définition: Un entier positif nest presque premier s'il peut être écrit sous la forme n=p^koù pest un nombre premier et kest également un entier positif. En d'autres termes, la factorisation première de nne contient que le même nombre.

Entrée: un entier positif2<=n<=2^31-1

Sortie: une valeur de vérité, si nest presque prime , et une valeur fausse, sinon.

Cas de test véridiques:

2
3
4
8
9
16
25
27
32
49
64
81
1331
2401
4913
6859
279841
531441
1173481
7890481
40353607
7528289

Cas de test falsifiés

6
12
36
54
1938
5814
175560
9999999
17294403

Veuillez ne pas utiliser les failles standard. C'est du code-golf donc la réponse la plus courte en octets l'emporte!

Answer 1

Sagemath , 2 octets

GF

Sorties via exception .

Essayez-le en ligne!

---

Le Sagemath intégré \$\text{GF}\$crée un champ d'ordre galoisien \$n\$. Cependant, rappelez-vous que \$\mathbb{F}_n\$est seulement un champ si \$n = p^k\$où \$p\$est un premier et \$k\$un entier positif. Ainsi, la fonction lève une exception si et seulement si son entrée n'est pas une puissance principale.

Answer 2

Python 2 , 42 octets

f=lambda n,p=2:n%p and f(n,p+1)or p**n%n<1

Essayez-le en ligne!

Puisque Python n'a pas de paramètres intégrés pour les nombres premiers, nous nous contentons de vérifier la divisibilité.

Nous trouvons le plus petit nombre premier pqui est un facteur de nen comptant jusqu'à p=2,3,4,...ce qu'il nsoit divisible par p, c'est-à- n%pdire zéro. Là, on vérifie que pc'est le seul facteur premier en vérifiant qu'une puissance élevée de pest divisible par n. Pour cela, p**nsuffit.

En tant que programme:

43 octets

n=input()
p=2
while n%p:p+=1
print p**n%n<1

Essayez-le en ligne!

Cela pourrait être plus court avec les codes de sortie si ceux-ci sont autorisés.

46 octets

lambda n:all(n%p for p in range(2,n)if p**n%n)

Essayez-le en ligne!

Answer 3

Langage de programmation Shakespeare , 329 octets

,.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

Essayez-le en ligne!

Sorties 0si l'entrée est presque première, et un entier positif dans le cas contraire. Je ne suis pas sûr que ce soit une sortie acceptable; le changer coûterait quelques octets.

Explication:

• Scène I: Pageprend en entrée (appelez ceci n). Initialisez Ajax = 1.
• Scène V: incrémenter Ajaxjusqu'à ce que Ajaxsoit un diviseur de Page; appeler la valeur finale pCeci donne le plus petit diviseur de Page, qui est garanti premier.
• Scène X: Cube Ajaxjusqu'à ce que vous vous retrouviez avec une puissance de p, disons p^klaquelle est supérieure à n. Ensuite, il ny a des ndivisions quasi-prime ssi p^k.

Answer 4

MATL , 4 octets

Yf&=

• Pour presque-nombres premiers, la sortie est une matrice contenant seulement 1s, ce qui est vrai .
• Sinon, la sortie est une matrice contenant plusieurs 1s et au moins un 0, ce qui est faux .

Essayez-le en ligne! Ou vérifiez tous les cas de test , y compris le test de véracité / fausseté.

Comment ça fonctionne

     % Implicit input
Yf   % Prime factors. Gives a vector with the possibly repeated prime factors
&=   % Matrix of all pair-wise equality comparisons
     % Implicit output

Answer 5

R , 36 32 29 octets

-3 octets en sortant un vecteur de booléens sans extraire le premier élément

!(a=2:(n=scan()))[!n%%a]^n%%n

Essayez-le en ligne!

Produit un vecteur de booléens. Dans R, un vecteur de booléens est vrai ssi le premier élément l'est TRUE.

Commencez par trouver le plus petit diviseur pde n. Nous pouvons le faire en vérifiant tous les nombres entiers (pas seulement les nombres premiers), car le plus petit diviseur d'un entier (à part 1) est toujours un nombre premier. Ici, asoit tous les entiers entre 2et n, alors p=a[!n%%a][1]est le premier élément adont se divise n.

Alors nest presque le premier si les ndivisions p^n.

Cela échoue pour toute entrée modérément grande, voici donc la version précédente qui fonctionne pour la plupart des entrées plus grandes:

R , 36 33 octets

!log(n<-scan(),(a=2:n)[!n%%a])%%1

Essayez-le en ligne!

Calculez le logarithme de nen base p: c'est un entier ssi nest presque premier.

Cela échouera en raison d'une imprécision en virgule flottante pour certaines entrées de grande taille (mais loin de toutes), en particulier pour un cas de test: \$4913=17^3\$.

Answer 6

C (gcc) , 43 octets

f(n,i){for(i=1;n%++i;);n=i<n&&f(n/i)^i?:i;}

Essayez-le en ligne!

Renvoie psi nest presque premier, et 1sinon.

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
}

Answer 7

Wolfram Language (Mathematica) , 11 octets

PrimePowerQ

Essayez-le en ligne!

@Sisyphus a sauvé 1 octet

Answer 8

05AB1E , 2 octets

ÒË

Essayez-le en ligne!

Commenté:

Ò   -- Are all the primes in the prime decomposition
 Ë  -- Equal?

Answer 9

J , ⁹ 8 octets

1=#@=@q:

Essayez-le en ligne!

-1 octet grâce à xash

Teste si l' auto-classification = des facteurs premiers q:a une longueur #égale à un1=

Answer 10

APL (Dyalog Classic) , 33 31 26 octets

{⍵∊∊(((⊢~∘.×⍨)1↓⍳)⍵)∘*¨⍳⍵}

-5 octets de la suggestion de Kevin Cruijssen.

Attention: très, très lent pour les grands nombres.

Explication

{⍵∊∊(((⊢~∘.×⍨)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)?

Essayez-le en ligne!

Answer 11

Pyth , 5 octets

!t{PQ

Essayez-le en ligne!

Explication:

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

Answer 12

Setanta , 61 59 octets

gniomh(n){p:=2nuair-a n%p p+=1nuair-a n>1 n/=p toradh n==1}

Essayez-le ici

Remarques:

• Le mot-clé correct est gníomh, mais Setanta permet de l'épeler sans les accents, alors je l'ai fait pour raser un octet.

Answer 13

Haskell , 36 octets

f n=mod(until((<1).mod n)(+1)2^n)n<1

Essayez-le en ligne!

36 octets

f n=and[mod(gcd d n^n)n<2|d<-[1..n]]

Essayez-le en ligne!

39 octets

f n=all((`elem`[1,n]).gcd n.(^n))[2..n]

Essayez-le en ligne!

39 octets

f n=mod n(n-sum[1|1<-gcd n<$>[1..n]])<1

Essayez-le en ligne!

40 octets

f n=and[mod(p^n)n<1|p<-[2..n],mod n p<1]

Essayez-le en ligne!

Answer 14

JavaScript (ES6), 43 octets

Sans BigInts

Renvoie une valeur booléenne.

f=(n,k=1)=>n%1?!~~n:f(n<0?n/k:n%++k?n:-n,k)

Essayez-le en ligne!

Une fonction récursive qui recherche d'abord le plus petit diviseur \$k>1\$de \$n\$puis divise \$-n\$par \$k\$jusqu'à ce que ce ne soit plus un entier. (La seule raison pour laquelle nous inversons le signe de \$n\$quand \$k\$ est trouvé pour faire la distinction entre les deux étapes de l'algorithme.)

Si \$n\$est presque premier, le résultat final est \$-\dfrac{1}{k}>-1\$. Alors on se retrouve avec \$\lceil n\rceil=0\$.

Si \$n\$n'est pas presque prime, il existe des \$q>k\$coprime avec \$k\$tel que \$n=q\times k^{m}\$. Dans ce cas, le résultat final est \$-\dfrac{q}{k}<-1\$. Alors on se retrouve avec \$\lceil n\rceil<0\$.

---

JavaScript (ES11), 33 octets

Avec BigInts

Avec BigInts, utiliser l'approche de @ xnor est probablement le chemin le plus court.

Renvoie une valeur booléenne.

f=(n,k=1n)=>n%++k?f(n,k):k**n%n<1

Essayez-le en ligne!

Answer 15

Retina 0.8.2 , 50 octets

.+
$* ^(?=(11+?)\1*$)((?=\1+$)(?=(1+)(\3+)$)\4)+1$

Essayez-le en ligne! Link inclut des cas de test plus rapides. Basé sur la réponse de @ Deadcode aux chaînes Match dont la longueur est une quatrième puissance . Explication:

.+
$*

Convertissez l'entrée en unaire.

^(?=(11+?)\1*$)

Commencez par faire correspondre le plus petit facteur \ $ p \ $ de \ $ n \ $ . ( \ $ p \ $ est forcément premier, bien sûr.)

(?=\1+$)(?=(1+)(\3+)$)

Alors que \ $ p | \ frac n {p ^ i} \ $ , trouve \ $ \ frac n {p ^ i} \ $ le plus grand facteur propre de \ $ \ frac n {p ^ {i + 1}} \ $ .

\4

La factorisation capture également \ $ (p - 1) \ frac n {p ^ {i + 1}} \ $ , qui est soustrait de \ $ \ frac n {p ^ i} \ $ , laissant \ $ \ frac n { p ^ {i + 1}} \ $ pour le prochain passage dans la boucle.

(...)+1$

Répétez la division par \$ p \$autant de fois que possible, puis vérifiez que \$ \frac n { p^k } = 1 \$.

Answer 16

Io , 48 octets

Réponse de R de @ RobinRyder.

method(i,c :=2;while(i%c>0,c=c+1);i log(c)%1==0)

Essayez-le en ligne!

Explication

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?
)

Answer 17

Assemblage (MIPS, SPIM) , 238 octets, 6 * 23 = 138 octets assemblés

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

Essayez-le en ligne!

Answer 18

Brachylog , 2 octets

Tous les facteurs premiers sont-ils égaux?

ḋ=

Essayez-le en ligne!

Answer 19

GAP 4.7, 31 octets

n->Length(Set(FactorsInt(n)))<2

Ceci est un lambda. Par exemple, l'instruction

Filtered([2..81], n->Length(Set(FactorsInt(n)))<2 );

donne la liste [ 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 ].

Essayez-le en ligne!

Answer 20

MathGolf , 10 octets

╒g¶mÉk╒#─╧

Port de la réponse APL (Dyalog Classic) de @Razetime, alors assurez-vous de le voter également!

Essayez-le en ligne.

Explication:

╒           # 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)

Answer 21

Facteur , 35 octets

: f ( n -- ? ) factors all-equal? ;

Essayez-le en ligne!

Answer 22

Japt , 6 octets

J'ai l'impression que cela devrait être 1 ou 2 octets plus court ...

k ä¶ ×

Essayez-le - inclut tous les cas de test

Answer 23

Java, 69 (ou 64?) Octets

n->{int c=0,t=1;for(;t++<n;)if(n%t<1)for(c++;n%t<1;)n/=t;return c<2;}

Essayez-le en ligne.

Explication:

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 nous étions autorisés à ignorer les inexactitudes en virgule flottante, un port de la réponse R de @ RobinRyder serait de 64 octets à la place:

n->{int m=1;for(;n%++m>0;);return Math.log(n)/Math.log(m)%1==0;}

Essayez-le en ligne.

Explication:

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

Mais malheureusement, cette approche échoue pour le cas de test 4913qui deviendrait 2.9999999999999996au lieu de 3.0dû à des inexactitudes en virgule flottante (elle réussit pour tous les autres cas de test).
Un correctif potentiel serait de 71 octets :

n->{int m=1;for(;n%++m>0;);return(Math.log(n)/Math.log(m)+1e9)%1<1e-8;}

Essayez-le en ligne.

Answer 24

Gelée , 3 octets

ÆfE

Essayez-le en ligne!

Answer 25

Burlesque , 6 octets

rifCsm

Essayez-le en ligne!

Explication:

ri      # Read integer from input
  fC    # Find its prime factorisation
    sm  # Are all values the same?