# Tag Info

227

hello, world!, 13 hello, world!

157

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: . ? ' . . . . . ....

123

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

99

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

68

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

66

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

66

Pyth, 4 bytes }QPQ Prints True or False.

59

Python (w/ PyPy JIT v1.9) ~1.9s Using a Multiple Polynomial Quadratic Sieve. I took this to be a code challenge, so I opted not to use any external libraries (other than the standard log function, I suppose). When timing, the PyPy JIT should be used, as it results in timings 4-5 times faster than that of cPython. Update (2013-07-29): Since originally ...

56

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 +... 55 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. 48 HTML+CSS, 254+nmax*28 bytes We can check primality using regular expressions. Mozilla has @document, which is defined as: @document [ <url> | url-prefix(<string>) | domain(<string>) | regexp(<string>) ]# { <group-rule-body> } To filter elements via CSS based on the current URL. This is a single pass, so we have to do two ... 47 Mathematica, 16 bytes CarmichaelLambda Well... 45 Help, WarDoq!, 1 byte P Outputs 1 if the input is prime, 0 otherwise. 43 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) ... 40 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: ? \ . " > " ! * + { & ' = < \ % ... 37 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 ... 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 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. 35 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%... 34 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 ... 33 Mathematica, 17 24 Just for comparison: Prime@Range@78498 As noted in a comment I failed to provide one prime per line; correction: Column@Prime@Range@78498 31 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. ... 29 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%... 27 Python 3, 46 bytes k=P=1 while k<1e6:P%k and print(k);P*=k*k;k+=1 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 the product. The ... 27 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 ... 27 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 ...

26

Haskell, 49 bytes Using xnor's Corollary to Wilson's Theorem: main=do n<-readLn;print$mod(product[1..n-1]^2)n>0 26 Jelly, 7 bytes Æn+Æp>Ḥ Try it online! Explanation See if Æn the next prime +Æp plus the previous prime >Ḥ is greater than 2n As a bonus, changing > to = or < checks for balanced and strong primes, respectively. 25 PHP, 117 characters This one is based on regular expressions. If a string containing$n characters can be split into chunks of equal length, then $n must be composite. (Assumes$n is a positive integer.) function p($n){$u=true;$s=str_repeat('x',$n);return($s!='x'&&!preg_match('/^(xx{'.$u.',})\\'.$u.'{'.$u.',}$/U',$s));} Output: for ($i=1;$i<=...

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