Zarte Primzahlen
Inspiriert von Find the größte fragile Prime .
Durch Entfernen von mindestens 1 Ziffer aus einer positiven Ganzzahl können wir eine andere nicht negative Ganzzahl erhalten. Beachten Sie, dass sich dies von der RemoveFunktion in der verknüpften Frage unterscheidet. Wir sagen, eine Primzahl ist empfindlich, wenn alle auf diese Weise erzeugten ganzen Zahlen keine Primzahlen sind. Zum Beispiel \$60649\$ generiert die folgenden Ganzzahlen:
0, 4, 6, 9, 49, 60, 64, 66, 69, 604, 606, 609, 649, 664, 669, 6049, 6064, 6069, 6649
Keine dieser ganzen Zahlen ist eine Primzahl, daher \$60649\$ist eine heikle Primzahl. Beachten Sie, dass alle führenden Nullen entfernt werden und dass die Anforderung "nicht prim" ist, also \$0\$und \$1\$beide qualifizieren sich, was bedeutet, dass zum Beispiel \$11\$ ist eine heikle Primzahl.
Ähnlich wie bei der Standard - Sequenz sind in der Regel Sie eine der folgenden Aufgaben:
- Bei einer positiven ganzen Zahl \$n\$, geben Sie zwei unterschiedliche, konsistente * Werte aus, je nachdem, ob \$n\$ ist eine heikle Primzahl oder nicht
- Bei einer positiven ganzen Zahl \$n\$, geben Sie das \ aus$n\$die zarte Blüte
- Bei einer positiven ganzen Zahl \$n\$, geben Sie das erste \ aus$n\$ zarte Primzahlen
- Geben Sie die Liste der empfindlichen Primzahlen unendlich aus
* : Sie können stattdessen zwei Wertesätze ausgeben, wobei die Werte im Satz der Definition von wahr und falsch in Ihrer Sprache entsprechen. Beispielsweise kann eine Python-Antwort eine leere Liste für Falsey / Truthy und ansonsten eine nicht leere Liste ausgeben.
Sie können auswählen, welche der Aufgaben Sie ausführen möchten.
Sie können auf jede Standardart eingeben und ausgeben , und da dies Code-Golf ist , gewinnt der kürzeste Code in Bytes
Als Referenz sind die ersten 20 empfindlichen Primzahlen:
2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949
Noch ein paar, auf die Sie achten sollten:
821 - False (Removing the 8 and the 1 gives 2 which is prime)
Ich werde eine 100 Prämie für eine Antwort bieten , welche Geräte eine der Standard - Sequenz I / O und nicht der Entscheidungsproblem Verfahren, die entweder:
- ist kürzer als eine naive Implementierung eines Entscheidungsproblems (bitte fügen Sie eine solche Version als Beweis bei, falls noch keine veröffentlicht wurde)
- oder das hängt nicht davon ab, ob beim Generieren von Werten überprüft wird, ob Werte empfindliche Primzahlen sind oder nicht (z. B. kann die Tatsache verwendet werden, dass nur bestimmte Ziffern auftreten können, oder etwas anderes, das nicht einfach eine "Schleife über Zahlen schlägt, empfindliche Primzahlen findet"). )
Dies ist ein bisschen subjektiv in Bezug auf das, was als "Überprüfen auf empfindliche Primzahlen" gilt, daher werde ich mein bestes Urteilsvermögen verwenden, wenn es um die Vergabe des Kopfgeldes geht.
Antworten
05AB1E , 4 Bytes
Code
Verwendet die 05AB1E- Codierung. Überprüft, ob die angegebene Zahl eine empfindliche Primzahl ist oder nicht.
æpJΘ
Probieren Sie es online aus! oder Suchen Sie nach allen Zahlen zwischen 1 und 9949 .
Erläuterung
æ # Get the powerset of the number.
p # Check for each element whether it is a prime.
J # Join these numbers into one big number.
Θ # Check whether this joined number is equal to 1.
APL (Dyalog Extended) , 16 bis 14 Byte
</1⍭⍎⍕(⊢,,¨)\⍞
-2 Bytes ( ∊⍎¨¨ → ⍎⍕) dank @ngn.
Vollständiges Programm, das eine einzelne Zahl aus stdin übernimmt und 1 (wahr) oder 0 (falsch) druckt.
Der Trick dabei ist, wie alle nicht leeren Teilsequenzen generiert werden:
(⊢,,¨)/ strgibt alle Teilsequenzen an, vonstrdenen das letzte Zeichen enthalten ist.
(⊢,,¨)/ '1234'
→ '1' (⊢,,¨) '2' (⊢,,¨) '3' (⊢,,¨) '4'
→ '1' (⊢,,¨) '2' (⊢,,¨) '4' '34'
→ '1' (⊢,,¨) '4' '34' '24' '234'
→ '4' '34' '24' '234' '14' '134' '124' '1234'
(⊢,,¨)\ strgilt(⊢,,¨)/für jedes Präfix vonstrund gibt alle nicht leeren Teilsequenzen als Liste von Listen von Zeichenfolgen an.
(⊢,,¨)\ '1234'
→ '1' ('2' '12') ('3' '23' '13' '123') ('4' '34' '24' '234' '14' '134' '124' '1234')
Erklärung des gesamten Codes:
</1⍭⍎⍕(⊢,,¨)\⍞
⍞ ⍝ Take n from stdin as a string
( )\ ⍝ For each prefix, reduce from right by
,¨ ⍝ prepend the previous char to each string
⊢, ⍝ and append to the previous list of strings
⍎⍕ ⍝ Convert nested strings to a single string,
⍝ and then eval it to get a simple integer vector
1⍭ ⍝ Test each number for primality
</ ⍝ Test if the only truth is the last one
Brachylog , 7 6 Bytes
ṗ⊇ᵘṗˢȮ
ṗ⊇ᵘṗˢȮ the implicit input
ṗ is a prime
⊇ᵘ and from every unique subset
ṗˢ select the primes
Ȯ and this should be a list with one element (the prime input itself)
Gelee , 7 Bytes
DŒPḌẒḄ’
Ein monadischer Link, der eine positive Ganzzahl akzeptiert, die Null (Falsey) zurückgibt, wenn es sich um eine empfindliche Primzahl handelt, oder eine Ganzzahl ungleich Null (Wahrhaftigkeit), wenn nicht.
Probieren Sie es online aus! Oder sehen Sie die ersten zwanzig .
Wie?
DŒPḌẒḄ’ - Link: n e.g. 824 409
D - decimal digits [8,2,4] [4,0,9]
ŒP - power-set [[],[8]...,[8,2,4]] [[],[4],...,[4,0,9]]
Ḍ - undecimal [0,8,2,4,82,84,24,824] [0,4,0,9,40,49,9,409]
Ẓ - is prime? [0,0,1,0,0,0,0,0] [0,0,0,0,0,0,0,1]
Ḅ - from binary 32 1
’ - decrement 31 0
Japt , 7 Bytes
¥à f_°j
Probieren Sie es aus oder testen Sie[0,1000)
¥à f_°j :Implicit input of integer string
¥ :Is equal to
à :Combinations
f :Filter
_ :By passing each through a function
° :Postfix increment, to cast to an integer
j :Is prime?
J , 25 23 Bytes
-2 danke an Jonah!
Gibt eine Liste zurück, die entweder 1 als wahr oder 0 als anderweitig enthält.
1</@p:(#~2#:@i.@^#)&.":
Wie es funktioniert
1</@p:(#~2#:@i.@^#)&.":
&.": convert the number to a string
( 2 ^#) 2 ^ length
#:@i.@ enumerated and to base 2
#~ select from the string based on the bit mask
&.": convert from strings to numbers
1 p: primes -> 1, non-primes -> 0
so in the delicate prime case, we have
(2^L) - 1 zeros and one 1 for the input itself
</@ reduce from left to right with less-than
(so last position is 1, everything else 0)
Pyth , 14 8 Bytes
qjfP_sTy
Erläuterung
qjfP_sTy
f # filter
y # all subsets of input
P_sT # with a primality test
j # join result of filter on newlines
q # check if it equals input
Retina 0,8,2 , 53 Bytes
^
;
+%`;(.)
$1;$'¶$`;
.+
$*
%A`^.?$|^(..+)\1+$
^1+¶+$
Probieren Sie es online aus! Link enthält Testfälle. Erläuterung:
^
;
+%`;(.)
$1;$'¶$`;
Generieren Sie alle Teilsequenzen der Eingabe.
.+
$*
Dann in unary konvertieren.
%A`^.?$|^(..+)\1+$
Löschen Sie diejenigen, die nicht prim sind, aber löschen Sie nicht die Zeilenumbrüche. (Ein mehrzeiliges Ersetzen funktioniert ebenfalls, es ist jedoch schwieriger, eine Erklärung dafür zu formatieren.)
^1+¶+$
Überprüfen Sie, ob die ursprüngliche Eingabe eine Primzahl war, aber keine der richtigen Teilsequenzen.
Scala , 173 170 Bytes
n=>(s"$n".indices.toSet.subsets.filter{x=>1<x.size&x.size<s"$n".size}.map(_.toSeq.sorted.map(""+n).mkString.toInt).toSet+n).filter{x=>x>1&2.to(x/2).forall(x%_>0)}==Set(n)
R , 163 154 Bytes
function(x,n=nchar(x),s=sum)(a=apply(!expand.grid(rep(list(0:1),n)),1,function(v)(y=s((x%/%10^(n:1-1)%%10)[v]*10^(s(v):1-1)))&s(!y%%1:y)==2))[1]&!s(a[-1])
Sucht nach Primzahlen unter den Zahlen, die durch Entfernen aller Ziffernkombinationen von x gebildet werden. Die erste Kombination ist das Entfernen ohne Ziffern: Dies muss WAHR sein, und alle anderen Prim-Tests müssen FALSCH sein.
Kommentiert:
is_delicate_prime=
function(x, # x = number to test
n=nchar(x), # n = number of digits of x
s=sum) # s = alias to sum() function
(a= # a = matrix of all prime-tests:
apply( # apply the function v to each of...
!expand.grid(rep(list(0:1),n)), # all combinations of n of TRUE/FALSE...
1, # row-by-row...
function(v) # defining the output of v as:
(y=s((x%/%10^(n:1-1)%%10) # the digits of x...
[v] # (considering only the elements chosen by v)...
*10^(s(v):1-1))) # multiplied by 10^((v-1)..0)...
&s(!y%%1:y)==2)) # tested for primality AND non-zero
[1] # Finally, output TRUE if a[1] is TRUE...
&!s(a[-1]) # and the sum of all other elements of a are FALSE
Wolfram Language (Mathematica) , 54 Bytes
Select[FromDigits/@Subsets@@RealDigits@#,PrimeQ]=={#}&
JavaScript (ES6), 98 95 Byte
Erwartet nals Zeichenfolge. Gibt einen booleschen Wert zurück.
n=>[...n].reduce((a,x)=>[...a,...a.map(y=>(g=k=>y%--k?g(k):(p+=q=y>1&k<2,y))(y+=x))],[p=0])|q/p
Wie?
Wir berechnen den Potenzsatz der Ziffern von nso, dass die Reihenfolge erhalten bleibt und nselbst zuletzt berechnet wird. Das Ergebnis ist wahr, wenn die einzige Primzahl unter den resultierenden ganzen Zahlen die letzte ist.
Python 2 , 139 \$\cdots\$ 145 142 Bytes
Es wurden 36 Bytes hinzugefügt, um einen Fehler zu beheben, auf den pxeger freundlicherweise hingewiesen hat .
5 Bytes dank pxeger gespart !!!
lambda n,R=range:all((g<2or any(g%i<1for i in R(2,g)))-(`g`==n)for g in{int(''.join(n[j]for j in R(len(n))if i>>j&1))for i in R(1,2**len(n))})
Gibt eine Ganzzahl als Zeichenfolge ein und gibt zurück, Trueob es sich um eine empfindliche Primzahl oder eine Falseandere handelt.
Python 3.8 (Vorabversion) , 146 144 Bytes
-2 Bytes durch Entfernen redundanter Klammern
Ich habe auch an einer sehr ähnlichen Antwort gearbeitet, kurz bevor Noodle9 ihre veröffentlicht hat, und ich habe Ideen daraus kombiniert, um diese zu erhalten ( stimme zu! ). Das ist jetzt ganz anders, weil sie anfangs ein kaputtes hatten, also dachte ich, ich würde meins posten.
lambda s,R=range:(l:=len(s))*all((g!=int(s))^(g>1)&all(g%k for k in R(2,g))for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l)})
Erläuterung:
lambda s,R=range:(l:=len(s))*all((g!=int(s))^(g>1)&all(g%k for k in R(2,g))for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l)})
lambda s : function
,R=range alias `range` built-in to `R`
{ s[j]for j in R(l)if i>>j&1 for i in R(1,2**l)} compute the power-set (excluding the empty set)
int(''.join( )) convert each list of digits to an integer
all( for g in ) check the integers for primality
all(g%k for k in R(2,g)) check for factors in the number
(g>1)& makes sure 0 and 1 aren't treated as prime
(g!=int(s))^ ensure the number itself is prime
(l:=len(s))* store the length in `l`
SageMath , 139 Bytes
def f(n):s=str(n);l=len(s);return p(n)*all(~-p(g)for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l-1)})
R=range;p=is_prime
Port meiner Python-Antwort.
Python 3 ,
Mit itertools und einem Golfrezept für powerset.
lambda s,R=range:all(p(int(''.join(t)),R)for t in sum(([*combinations(s,k)]for k in R(1,len(s))),[]))>p(int(s),R)
from itertools import*
p=lambda n,R:any(n%i<1for i in R(2,n))or 2>n
Erwartet die Eingabe als Zeichenfolge.
Die Funktion gibt pzurück, Truewenn ihre Eingabe keine Primzahl ist und Falsewenn sie Primzahl ist. Die Hauptfunktion gibt zurück, (forall t, p(t)) > p(s)wo talle "Unterwerte" von s. Die einzige Möglichkeit für Boolesche, diese Ungleichung zu befriedigen, ist True > False, dass alle Nicht-Primzahlen tsind und skeine Nicht-Primzahlen sind.
Haftungsausschluss: Es gab bereits zwei Python-Antworten, als ich diese veröffentlichte.