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 ...
answered Aug 19 '14 at 0:16
aditsu quit because SE is EVIL
22.6k4 gold badges54 silver badges101 bronze badges
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