239
hello, world!, 13
hello, world!
159
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:
. ? ' .
. . . . ....
129
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.5k44 gold badges5353 silver badges100100 bronze badges
70
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 ...
answered Aug 20 '14 at 19:31
Martin Ender
188k6262 gold badges416416 silver badges923923 bronze badges
69
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 ...
answered Sep 11 '15 at 21:22
Martin Ender
188k6262 gold badges416416 silver badges923923 bronze badges
68
Pyth, 4 bytes
}QPQ
Prints True or False.
67
Python (w/ pypy2 v7.3.1) ~0.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 posting, ...
60
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 ...
answered Sep 11 '15 at 14:12
Martin Ender
188k6262 gold badges416416 silver badges923923 bronze badges
60
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)...
53
CJam, 4 bytes
qimp
CJam has a built-in operator for primality testing.
51
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 ...
49
Mathematica, 16 bytes
CarmichaelLambda
Well...
answered Sep 18 '16 at 18:34
Martin Ender
188k6262 gold badges416416 silver badges923923 bronze badges
48
Help, WarDoq!, 1 byte
P
Outputs 1 if the input is prime, 0 otherwise.
45
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:
? \ . "
> " ! * +
{ &...
45
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) ...
45
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.
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
...
answered Sep 18 '15 at 19:47
Martin Ender
188k6262 gold badges416416 silver badges923923 bronze badges
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
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 ...
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.
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.
...
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'(...
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%n<...
27
Haskell, 49 bytes
Using xnor's Corollary to Wilson's Theorem:
main=do n<-readLn;print$mod(product[1..n-1]^2)n>0
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
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
Related Tags
primes × 288code-golf × 247
math × 77
number-theory × 76
number × 56
sequence × 56
decision-problem × 28
code-challenge × 25
integer × 16
factoring × 16
fastest-code × 11
arithmetic × 10
restricted-source × 10
string × 8
kolmogorov-complexity × 7
fibonacci × 7
binary × 6
base-conversion × 6
cops-and-robbers × 6
ascii-art × 5
source-layout × 5
combinatorics × 4
date × 4
palindrome × 4
array-manipulation × 3