Ist es fast Prime?

Question

Sandkasten

Definition: Eine positive ganze Zahl nist fast-prime , wenn es in der Form geschrieben werden , n=p^kwo peine Primzahl ist und kist auch eine positive ganze Zahlen. Mit anderen Worten, die Primfaktorisierung von nenthält nur die gleiche Zahl.

Eingabe: Eine positive ganze Zahl2<=n<=2^31-1

Ausgang: ein truthy Wert, wenn nist fast-prime und ein falsy Wert, wenn nicht.

Truthy Test Cases:

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

Falsche Testfälle

6
12
36
54
1938
5814
175560
9999999
17294403

Bitte verwenden Sie keine Standardlücken. Dies ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes!

Answer 1

Sagemath , 2 Bytes

GF

Ausgaben über Ausnahme .

Probieren Sie es online aus!

---

Der Sagemath gebaut \$\text{GF}\$erstellt ein Galois- Ordnungsfeld \$n\$. Denken Sie jedoch daran, dass \$\mathbb{F}_n\$ist nur ein Feld, wenn \$n = p^k\$wo \$p\$ist eine Primzahl und \$k\$eine positive ganze Zahl. Daher löst die Funktion genau dann eine Ausnahme aus, wenn ihre Eingabe keine Primzahl ist.

Answer 2

Python 2 , 42 Bytes

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

Probieren Sie es online aus!

Da Python keine eingebauten Primzahlen hat, müssen wir die Teilbarkeit überprüfen.

Wir finden die kleinste Primzahl , pdie ein Faktor ist ndurch das Zählen bis p=2,3,4,...bis nteilbar ist p, dh n%pgleich Null ist . Dort überprüfen wir, ob dies pder einzige Primfaktor ist, indem wir überprüfen, ob eine hohe Potenz von pdurch teilbar ist n. Dafür p**ngenügt.

Als Programm:

43 Bytes

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

Probieren Sie es online aus!

Dies kann bei Exit-Codes kürzer sein, wenn diese zulässig sind.

46 Bytes

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

Probieren Sie es online aus!

Answer 3

Shakespeare-Programmiersprache , 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

Probieren Sie es online aus!

Gibt aus, 0wenn der Eingang fast prim ist, andernfalls eine positive Ganzzahl. Ich bin nicht sicher, ob dies eine akzeptable Ausgabe ist. Das Ändern würde einige Bytes kosten.

Erläuterung:

• Szene I: PageNimmt Eingaben auf (nennen Sie dies n). Initialisieren Ajax = 1.
• Szene V: Inkrementieren, Ajaxbis Ajaxein Teiler von ist Page; call the final value pDies ergibt den kleinsten Teiler von Page, der garantiert eine Primzahl ist.
• Szene X: Würfel, Ajaxbis du eine Potenz von hast p, p^kdie größer ist als n. Dann nist fast Prime iff nteilt p^k.

Answer 4

MATL , 4 Bytes

Yf&=

• Für Fast-Primzahlen ist die Ausgabe eine Matrix, die nur 1s enthält, was wahr ist .
• Andernfalls ist die Ausgabe eine Matrix, die mehrere 1s und mindestens eine enthält 0, was falsch ist .

Probieren Sie es online aus! Oder überprüfen Sie alle Testfälle , einschließlich Wahrheits- / Falschheitsprüfung.

Wie es funktioniert

     % 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 Bytes

-3 Bytes durch Ausgabe eines Booleschen Vektors, ohne das erste Element zu extrahieren

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

Probieren Sie es online aus!

Gibt einen Vektor von Booleschen Werten aus. In R ist ein Vektor von Booleschen Werten wahr, wenn das erste Element ist TRUE.

Finden Sie zuerst den kleinsten Teiler pvon n. Wir können dies tun, indem wir alle ganzen Zahlen (nicht nur Primzahlen) überprüfen, da der kleinste Teiler einer ganzen Zahl (außer 1) immer eine Primzahl ist. Hier seien aalle ganzen Zahlen zwischen 2und n, dann teilt p=a[!n%%a][1]sich das erste Element .an

Dann nist fast Prime iff nteilt p^n.

Dies schlägt bei mäßig großen Eingaben fehl. Hier ist die vorherige Version, die für die meisten größeren Eingaben funktioniert:

R , 36 33 Bytes

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

Probieren Sie es online aus!

Berechnen Sie den Logarithmus von nin base p: Dies ist eine Ganzzahl, wenn if nfast eine Primzahl ist.

Dies schlägt aufgrund der Gleitkomma-Ungenauigkeit für bestimmte (aber bei weitem nicht alle) große Eingaben fehl, insbesondere für einen Testfall: \$4913=17^3\$.

Answer 6

C (gcc) , 43 Bytes

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

Probieren Sie es online aus!

Gibt zurück, pwenn nfast Prime ist, und 1ansonsten.

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 Bytes

PrimePowerQ

Probieren Sie es online aus!

@Sisyphus hat 1 Byte gespeichert

Answer 8

05AB1E , 2 Bytes

ÒË

Probieren Sie es online aus!

Kommentiert:

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

Answer 9

J , ⁹ 8 Bytes

1=#@=@q:

Probieren Sie es online aus!

-1 Byte dank xash

Testet, ob die Selbstklassifizierung = der Primfaktoren q:eine Länge #von eins hat1=

Answer 10

APL (Dyalog Classic) , 33 31 26 Byte

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

-5 Bytes von Kevin Cruijssens Vorschlag.

Warnung: Sehr, sehr langsam für größere Zahlen.

Erläuterung

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

Probieren Sie es online aus!

Answer 11

Pyth , 5 Bytes

!t{PQ

Probieren Sie es online aus!

Erläuterung:

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 Bytes

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

Probieren Sie es hier aus

Anmerkungen:

• Das richtige Schlüsselwort ist gníomh, aber Setanta erlaubt die Rechtschreibung ohne Akzente, also habe ich dies getan, um ein Byte zu rasieren.

Answer 13

Haskell , 36 Bytes

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

Probieren Sie es online aus!

36 Bytes

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

Probieren Sie es online aus!

39 Bytes

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

Probieren Sie es online aus!

39 Bytes

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

Probieren Sie es online aus!

40 Bytes

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

Probieren Sie es online aus!

Answer 14

JavaScript (ES6), 43 Byte

Ohne BigInts

Gibt einen booleschen Wert zurück.

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

Probieren Sie es online aus!

Eine rekursive Funktion, die ersten Blicke für den kleinsten Teiler \$k>1\$von \$n\$und teilt dann \$-n\$von \$k\$bis es keine ganze Zahl mehr ist. (Der einzige Grund, warum wir das Vorzeichen von \ umkehren$n\$wenn \$k\$ gefunden wird, um zwischen den beiden Schritten des Algorithmus zu unterscheiden.)

If \$n\$ist fast Prime, das Endergebnis ist \$-\dfrac{1}{k}>-1\$. Also landen wir bei \$\lceil n\rceil=0\$.

If \$n\$ist nicht fast Prime, es gibt einige \$q>k\$Koprime mit \$k\$so dass \$n=q\times k^{m}\$. In diesem Fall ist das Endergebnis \$-\dfrac{q}{k}<-1\$. Also landen wir bei \$\lceil n\rceil<0\$.

---

JavaScript (ES11), 33 Byte

Mit BigInts

Bei BigInts ist die Verwendung des Ansatzes von @ xnor wahrscheinlich der kürzeste Weg.

Gibt einen booleschen Wert zurück.

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

Probieren Sie es online aus!

Answer 15

Retina 0,8,2 , 50 Bytes

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

Probieren Sie es online aus! Link enthält schnellere Testfälle. Basierend auf der Antwort von @ Deadcode auf Match-Strings, deren Länge eine vierte Potenz ist . Erläuterung:

.+
$*

Konvertieren Sie die Eingabe in unär.

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

Beginnen Sie, indem Sie den kleinsten Faktor \ $ p \ $ von \ $ n \ $ abgleichen . ( \ $ p \ $ ist natürlich unbedingt eine Primzahl.)

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

Während \ $ p | \ frac n {p ^ i} \ $ , finde \ $ \ frac n {p ^ i} \ $ den größten richtigen Faktor, der notwendigerweise \ $ \ frac n {p ^ {i + 1}} \ $ ist .

\4

Die Faktorisierung erfasst auch \ $ (p - 1) \ frac n {p ^ {i + 1}} \ $ , das von \ $ \ frac n {p ^ i} \ $ subtrahiert wird , wobei \ $ \ frac n { übrig bleibt p ^ {i + 1}} \ $ für den nächsten Durchgang durch die Schleife.

(...)+1$

Wiederholen Sie die Division durch \$ p \$Überprüfen Sie dann so oft wie möglich, dass \$ \frac n { p^k } = 1 \$.

Answer 16

Io , 48 Bytes

Port von @ RobinRyder's R Antwort.

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

Probieren Sie es online aus!

Erläuterung

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

Assembly (MIPS, SPIM) , 238 Bytes, 6 * 23 = 138 zusammengesetzte Bytes

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

Probieren Sie es online aus!

Answer 18

Brachylog , 2 Bytes

Sind alle Primfaktoren gleich?

ḋ=

Probieren Sie es online aus!

Answer 19

GAP 4.7, 31 Bytes

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

Dies ist ein Lambda. Zum Beispiel die Aussage

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

ergibt die 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 ].

Probieren Sie es online aus!

Answer 20

MathGolf , 10 Bytes

╒g¶mÉk╒#─╧

Port of @Razetime 's APL (Dyalog Classic) Antwort , also stellen Sie sicher, dass Sie ihn ebenfalls positiv bewerten!

Probieren Sie es online aus.

Erläuterung:

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

Faktor 35 Bytes

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

Probieren Sie es online aus!

Answer 22

Japt , 6 Bytes

Ich denke, das sollte 1 oder 2 Bytes kürzer sein ...

k ä¶ ×

Probieren Sie es aus - enthält alle Testfälle

Answer 23

Java, 69 (oder 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;}

Probieren Sie es online aus.

Erläuterung:

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

---

Wenn wir Gleitkomma-Ungenauigkeiten ignorieren könnten, wäre ein Port der @ RobinRyder-R-Antwort stattdessen 64 Byte :

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

Probieren Sie es online aus.

Erläuterung:

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

Leider schlägt dieser Ansatz für Testfälle fehl, 4913die 2.9999999999999996anstelle von 3.0Gleitkomma-Ungenauigkeiten auftreten würden (er ist für alle anderen Testfälle erfolgreich).
Ein möglicher Fix wäre 71 Bytes :

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

Probieren Sie es online aus.

Answer 24

Gelee , 3 Bytes

ÆfE

Probieren Sie es online aus!

Answer 25

Burlesque , 6 Bytes

rifCsm

Probieren Sie es online aus!

Erläuterung:

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