# Tag Info

## Hot answers tagged primes

248

hello, world!, 13 hello, world!

163

Hexagony, 29 bytes .?'.).@@/'/.!.>+=(<.!)}($>(<% The readable version of this code is: . ? ' . ) . @ @ / ' / . ! . > + = ( < . ! ) } ($ > ( < % . . . . . . . . Explanation: It test if there is a number from 2 to n-1 who divides n. Initialization: Write n in one memory cell and n-1 in an other: . ? ' . . . . . ....

132

C, 0.026119s (Mar 12 2016) #include <math.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define cache_size 16384 #define Phi_prec_max (47 * a) #define bit(k) (1ULL << ((k) & 63)) #define word(k) sieve[(k) >> 6] #define sbit(k) ((word(k >> 1) >...

100

CJam - 13 q~,>{mfW=}$0= Try it at http://cjam.aditsu.net/ Example input: 2001 2014 Example output: 2002 Explanation: q~ reads and evaluates the input, pushing the 2 numbers on the stack (say min and max) , makes an array [0 1 ... max-1] > slices the array starting at min, resulting in [min ... max-1] {…}$ sorts the array using the block to ...

71

Regex (.NET PCRE flavour), 183 129 bytes Don't try this at home! This is not really a contender for the win. But Eric Tressler suggested solving this problem with nothing but a regex, and I couldn't resist giving it a go. This might be is possible in PCRE as well (and even shorter, see below), but I chose .NET because my solution needs arbitrary-length ...

71

Hexagony, 218 92 58 55 bytes Notice: This answer has been solidly beaten with a side-length 4 solution by Etoplay. )}?}.=(..]=}='.}.}~./%*..&.=&{.<......=|>(<..}!=...&@\[ The first ever non-trivial (i.e. non-linear) Hexagony program! It is based on the same squared-factorial approach as Sp3000's Labyrinth answer. After starting out ...

69

Pyth, 4 bytes }QPQ Prints True or False.

64

Python 2, 61 47 bytes lambda n:[k/n for k in range(n*n)if k/n*k%n==1] Try it online! Background Consider the ring $(Z_n, +_n, \cdot_n)$. While this ring is usually defined using residue classes modulo $n$, it can also be thought of as the set $Z_n = \{0, \dots, n - 1\}$, where the addition and multiplication operators are defined by $a +_n b = (a + b)... 63 Retina, 16 bytes ^(?!(..+)\1+).. Try it online! Let's start with a classic: detecting primes with a regex. Input should be given in unary, using any repeated printable character. The test suite includes a conversion from decimal to unary for convenience. A Retina program consisting of a single line treats that line as a regex and prints the number of ... 52 CJam, 4 bytes qimp CJam has a built-in operator for primality testing. 50 Sagemath, 2 bytes GF Outputs via exception. Try it online! The Sagemath builtin$\text{GF}$creates a Galois Field of order$n$. However, remember that$\mathbb{F}_n$is only a field if$n = p^k$where$p$is a prime and$k$a positive integer. Thus the function throws an exception if and only if its input is not a prime power. 49 Hexagony, 28 bytes Since Etoplay absolutely trounced me on this question, I felt that I had to outgolf his only other answer. ?\.">"!*+{&'=<\%(><.*.'(@>'/ Try it online! I use Wilson's Theorem, like Martin did in his answer: Given n, I output (n-1!)² mod n Here it the program unfolded: ? \ . " > " ! * + { &... 49 Mathematica, 16 bytes CarmichaelLambda Well... 48 Help, WarDoq!, 1 byte P Outputs 1 if the input is prime, 0 otherwise. 46 Regex (.NET), 122 113 bytes ^(?=((?=.*(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))((?=.*(?=\6)(?<=(?!(.+.)\8*(?=\6)(?<=^\8+))(.+?(?>\9?)))).)+ Assuming input and output are in unary, and the output is taken from the main match of the regex. Breakdown of the regex: ^(?=((?=.*(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*)) calculates π̅(x) ... 38 Python 3, 45 bytes k=P=1 while k<1e6:P%k>0==print(k);P*=k*k;k+=1 Try it online! By the time the loop reaches testing k, it has iteratively computed the squared-factorial P=(k-1)!^2. If k is prime, then it doesn't appear in the product 1 * 2 * ... * (k-1), so it's not a factor of P. But, if it's composite, all its prime factors are smaller and so in ... 38 Mornington Crescent, 2448 bytes We're back in London! Take Northern Line to Bank Take Circle Line to Bank Take District Line to Parsons Green Take District Line to Bank Take Circle Line to Hammersmith Take District Line to Upney Take District Line to Hammersmith Take Circle Line to Victoria Take Victoria Line to Seven Sisters Take Victoria Line to Victoria ... 38 Jelly, 8 bytes 44‘²!*ḍ@ Try it online! Note that test cases 11111 and above are a bit too much for TIO. Verification  source="34,34,fc,82,21,2a,d5,40"  xxd -ps -r > 2017.jelly <<< source  xxd -g 1 2017.jelly 0000000: 34 34 fc 82 21 2a d5 40 44..!*.@  eval printf '"%d "' 0x{source}; echo # Code points in decimal ... 37 05AB1E, 3 bytes !fg This assumes that factorization built-ins are allowed. Try it online! How it works ! Compute the factorial of the input. f Determine its unique prime factors. g Get the length of the resulting list. 36 CJam, score 276496.9062958626 2,128*_(]128* It turns out to be optimal, because: There aren't any non-orthogonal pairs with distance 2. So the distance must be odd, and so is the distance squared. As p2=x2+y2, one of x and y (squared or not) must be odd, and the other must be even. Those points are always in the opposite color in this image. This and its ... 36 43 bytes (4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n<1 Try it online! The method is similar to Dennis' second (deleted) answer, but this answer is easier to be proved correct. Proof Short form The most significant digit of (4**n+1)**n%4**n**2 in base$2^n$that is not divisible by$n$will make the next (less significant) digit in (4**n+1)**n%... 33 Jelly, 74 71 69 68 66 bytes “©ạ-3ṗÇñ"ỤḍV8żṢ?ḤsMVE[,Ṃƭ"ḞÇsẇʂ(ụFsẠʂẆŀṣ’ḃ19ĖŒṙị⁾81s30m0Z062 ȷ446‘ Try it online! How it works The literal “©ạ-3ṗÇñ"ỤḍV8żṢ?ḤsMVE[,Ṃƭ"ḞÇsẇʂ(ụFsẠʂẆŀṣ’ replaces all characters with their code points in Jelly's code page and interprets the result as a (bijective) base-250 number, yielding the following integer. ... 31 hello, world!, 13 bytes, 1193 hello, world! 30 Score 100 8605 I used an algorithm that starts with one solution and repeatedly tries to split a prime$p$in the solution into two other primes$q_ 1$and$q_ 2$that satisfy$\frac1{p-1} = \frac1{q_1-1}+\frac1{q_2-1}$. It is known (and can be quickly checked) that the positive integer solutions to$\frac1n = \frac1x + \frac1y\$are in one-to-one ... 29 Brachylog (V2), 1 byte ṗ Try it online! Brachylog (V1), 2 bytes #p This uses the built-in predicate #p - Prime, which constrains its input to be a prime number. Brachylog is my attempt at making a Code Golf version of Prolog, that is a declarative code golf language that uses backtracking and unification. Alternate solution with no built-in: 14 bytes ybbrb'(... 28 Haskell, 49 bytes Using xnor's Corollary to Wilson's Theorem: main=do n<-readLn;print$mod(product[1..n-1]^2)n>0

28

GS2, 12 10 bytes V@'◄l.1&‼l The source code uses the CP437 encoding. Try it online! Test run $xxd -r -ps <<< 564027116c2e3126136c > phinotpi.gs2$ wc -c phinotpi.gs2 10 phinotpi.gs2 \$ gs2 phinotpi.gs2 <<< 1000 552 How it works V Read an integer n from STDIN. @ Push a copy of n. ' Increment the copy ...

28

Python, 76 73 67 bytes f=lambda n,k=1:1-any(a**-~k*~-a**k%n for a in range(n))or-~f(n,k+1) Try it online! A further byte could be saved by returning True instead of 1. Alternative implementation Using the same approach, there is also the following implementation by @feersum which doesn't use list comprehensions. f=lambda n,k=1,a=1:a/n or(a**-~k*~-a**k%n<...

26

Labyrinth, 29 bytes 1 ? : } +{%!@ (:'( } { :** Reads an integer from STDIN and outputs ((n-1)!)^2 mod n. Wilson's theorem is pretty useful for this challenge. The program starts at the top-left corner, beginning with 1 which multiplies the top of the stack by 10 and adds 1. This is Labyrinth's way of building large numbers, but since Labyrinth's stacks ...

Only top voted, non community-wiki answers of a minimum length are eligible