Ihr Ziel ist es festzustellen, ob eine bestimmte Zahl n
in den wenigsten Bytes eine Primzahl ist. Ihr Code muss jedoch ein einzelner Python 2- Ausdruck sein, der nur aus Zahlen besteht
- Betreiber
- die Eingangsvariable
n
- ganzzahlige Konstanten
- Klammern
Keine Schleifen, keine Zuweisungen, keine eingebauten Funktionen, nur das, was oben aufgeführt ist. Ja es ist möglich.
Betreiber
Hier ist eine Liste aller Operatoren in Python 2 , einschließlich arithmetischer, bitweiser und logischer Operatoren:
+ adddition
- minus or unary negation
* multiplication
** exponentiation, only with non-negative exponent
/ floor division
% modulo
<< bit shift left
>> bit shift right
& bitwise and
| bitwise or
^ bitwise xor
~ bitwise not
< less than
> greater than
<= less than or equals
>= greater than or equals
== equals
!= does not equal
Alle Zwischenwerte sind Ganzzahlen (oder False / True, was implizit 0 und 1 entspricht). Exponentiation darf nicht mit negativen Exponenten verwendet werden, da dies zu Floats führen kann. Beachten Sie, dass /
die Unterteilung im Gegensatz zu Python 3 //
nicht erforderlich ist.
Auch wenn Sie nicht mit Python vertraut sind, sollten die Operatoren ziemlich intuitiv sein. In dieser Tabelle finden Sie die Rangfolge der Operatoren sowie in diesem und dem folgenden Abschnitt eine detaillierte Beschreibung der Grammatik. Sie können Python 2 unter TIO ausführen .
I / O
Eingabe: Eine positive Ganzzahl n
, die mindestens 2 ist.
Ausgang: 1 wenn n
Primzahl und 0 sonst. True
und False
kann auch verwendet werden. Wenigste Bytes gewinnt.
Da es sich bei Ihrem Code um einen Ausdruck handelt, handelt es sich um ein Snippet, bei dem der Eingabewert als gespeichert n
und die gewünschte Ausgabe ausgewertet wird.
Ihr Code muss für n
beliebig große Systemgrenzen funktionieren. Da der Ganzzahltyp von Python unbegrenzt ist, sind den Operatoren keine Grenzen gesetzt. Es kann jedoch lange dauern, bis Ihr Code ausgeführt wird.
Antworten:
43 Bytes
Probieren Sie es online!
Die Methode ähnelt der zweiten (gelöschten) Antwort von Dennis, aber diese Antwort lässt sich leichter als richtig erweisen.
Beweis
Kurzform
Die höchstwertige Ziffer2n , die nicht durch teilbar ist, ergibt n die nächste (niedrigere) Ziffer
(4**n+1)**n%4**n**2
in der Basis(4**n+1)**n%4**n**2/n
ungleich Null (wenn diese "nächste Ziffer" nicht im Bruchteil liegt), dann a&
mit der Bitmaske2**(2*n*n+n)/-~2**n
wird zur Überprüfung ausgeführt Wenn eine Ziffer an einer ungeraden Position ungleich Null ist.Lange Form
Sei die Zahl mit der Darstellung der Basis b , dh a n b n + ⋯ + a 1 b 1 + a 0 b 0 , und a i sei die Ziffer bei Position " i " in der Darstellung der Basis b .[an,…,a1,a0]b b anbn+⋯+a1b1+a0b0 ai i b
Weil (mitn22n×4n2−11+2n=2n(2n−1)×(4n)n−14n−1=[2n−1,0,2n−1,0,2n−1,0]2n n s) ist eine ganze Zahl und ≤ 2 n2n−1 ,
=[2n-1,0,2n-1,0,2n-1,0]2n.⌊2n1+2n⌋=0 [2n−1,0,2n−1,0,2n−1,0]2n
2**(2*n*n+n)/-~2**n
Als nächstes betrachten
, alsowird die Zahl auf 2 n letzte Stellen gekürzt - das schließt das ( n) aus4n2=(2n)2n 2n (ist 1), enthält aber alle anderen Binomialkoeffizienten.(nn)
%4**n**2
Über
/n
:Wenn eine Primzahl ist, ist das Ergebnis [n . Alle Ziffern an der ungeraden Position sind Null.[(nn−1)/n,0,…,0,(n1)/n,0,0]2n
Wenn keine Primzahl ist:n
Sei die größte ganze Zahl, so dass n ∤ ( na (n>a>0). Schreiben Sie die Dividende um alsn∤(na) n>a>0
The first summand has all digits divisible byn , and the digit at position 2a−1 zero.
The second summand has its most significant digit (at position2a ) not divisible by n and (the base) 2n>n , so the quotient when dividing that by n would have the digit at position 2a−1 nonzero.
Therefore, the final result (2n , of course) at position 2a+1 nonzero.
(4**n+1)**n%4**n**2/n
) should have the digit (baseFinally, the bitwise AND (2n (because the base is a power of 2), and because a&0=0,a&(2n−1)=a for all 0≤a<2n , n odd positions zero - which is equivalent to n being prime.
&
) performs a vectorized bitwise AND on the digits in base(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n
is zero iff(4**n+1)**n%4**n**2/n
has all digits in firstquelle
(4**n+1)**n%2**n**2/n&2**n**2/-~2**n<1
work?n
not to cause unwanted interactions between the digits base4**n
.(4**n+1)**n%4**n**2/n<<n&4**n**2/-~2**n<1
. Ich bin gespannt, ob diese Herausforderung ohne bitweise Operatoren möglich ist.Python 2, 56 bytes
Try it online!
Dies ist ein Proof-of-Concept, dass diese Herausforderung nur mit arithmetischen Operatoren, insbesondere ohne bitweise, durchgeführt werden kann
|
,&
, or^
. The code uses bitwise and comparison operators only for golfing, and they can easily be replaced with arithmetic equivalents.Die Lösung ist jedoch extrem langsam und ich konnte nicht ausführenn=6 2nn .
The main idea is to make an expression for the factorialn! , which lets us do a Wilson's Theorem primality test (n−1)!%n>n−2 where % is the modulo operator.
We can make an expression for the binomial coefficient, which is made of factorials
But it's not clear how to extract just one of these factorials. The trick is to hammer apartn! by making m really huge.
So, if we letc be the product (1−1m)(1−2m)⋯(1−n−1m) , we have
If we could just ignorec , we'd be done. The rest of this post is looking how large we need to make m to be able to do this.
Note thatc approaches 1 from below as m→∞ . We just need to make m huge enough that omitting c gives us a value with integer part n! so that we may compute
For this, it suffices to have1−c<1/n! to avoid the ratio passing the next integer n!+1 .
Observe thatc is a product of n terms of which the smallest is (1−n−1m) . So, we have
which means1−c<n2m . Since we're looking to have 1−c<1/n! , it suffices to take m≥n!⋅n2 .
In the code, we usem=nn . Since Wilson's Theorem uses (n−1)! , we actually only need m≥(n−1)!⋅(n−1)2 . It's easy to see that m=nn satisfies the bound for the small values and quickly outgrows the right hand side asymptotically, say with Stirling's approximation.
quelle
This answer doesn't use any number-theoretic cleverness. It spams Python's bitwise operators to create a manual "for loop", checking all pairs1≤i,j<n to see whether i×j=n .
Python 2, way too many bytes (278 thanks to Jo King in the comments!)
Try it online!
This is a lot more bytes than the other answers, so I'm leaving it ungolfed for now. The code snippet below contains functions and variable assignment for clarity, but substitution turns isPrime(n) into a single Python expression.
Why does it work?
I'll do the same algorithm here in base 10 instead of binary. Look at this neat fraction:
If we put a large power of 10 in the numerator and use Python's floor division, this gives an enumeration of numbers. For example,1015/(9992)=1002003004 with floor division, enumerating the numbers 1,2,3,4 .
Let's say we multiply two numbers like this, with different spacings of zeroes. I'll place commas suggestively in the product.
The product enumerates, in three-digit sequences, the multiplication table up to 4 times 4. If we want to check whether the number 5 is prime, we just have to check whether005 appears anywhere in that product.
To do that, we XOR the above product by the number005005005…005 , and then subtract the number 001001001…001 . Call the result d . If 005 appeared in the multiplication table enumeration, it will cause the subtraction to carry over and put 999 in the corresponding place in d .
To test for this overflow, we compute an AND ofd and the number 900900900…900 . The result is zero if and only if 5 is prime.
quelle