Hot answers tagged

139 votes

Calculate the number of primes up to n

C, 0.026119s (Mar 12 2016) ...
Dennis's user avatar
  • 210k
67 votes

Coprimes up to N

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 ...
Dennis's user avatar
  • 210k
53 votes

Is this number a prime?

Hexagony, 28 bytes Since Etoplay absolutely trounced me on this question, I felt that I had to outgolf his only other answer. ...
H.PWiz's user avatar
  • 11.6k
51 votes
Accepted

Is it almost-prime?

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 \$\...
Sisyphus's user avatar
  • 14.7k
49 votes

Compute the Carmichael function

Mathematica, 16 bytes CarmichaelLambda Well...
Martin Ender's user avatar
41 votes
Accepted

Prime counting function

05AB1E, 3 bytes !fg This assumes that factorization built-ins are allowed. Try it online! How it works ...
Dennis's user avatar
  • 210k
39 votes
Accepted

Determine whether a number is 2017-friable without primes in your source code

Jelly, 8 bytes 44‘²!*ḍ@ Try it online! Note that test cases 11111 and above are a bit too much for TIO. Verification ...
Dennis's user avatar
  • 210k
39 votes

Primality testing formula

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 ...
DELETE_ME's user avatar
  • 17.3k
37 votes

A prime test that's LITERALLY prime

hello, world!, 13 bytes, 1193 hello, world!
Gurupad Mamadapur's user avatar
34 votes
Accepted

Output the Trinity Hall Prime

Jelly, 74 71 69 68 66 bytes “©ạ-3ṗÇñ"ỤḍV8żṢ?ḤsMVE[,Ṃƭ"ḞÇsẇʂ(ụFsẠʂẆŀṣ’ḃ19ĖŒṙị⁾81s30m0Z062 ȷ446‘ Try it online! How it works The literal ...
Dennis's user avatar
  • 210k
30 votes
Accepted

Longest Prime Sums

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} = \...
Greg Martin's user avatar
  • 15.4k
28 votes

Compute the Carmichael function

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 ...
Dennis's user avatar
  • 210k
27 votes

Recognize most smaller primes with a regex

90 79 72 67 65 64 bytes ^(?!([258][0369]*[147]|[1475][258]|[147]{3}|[0369])+$)\d+[1379]$ Matches 2–3-digit numbers not divisible by 2, 3, or 5, with an added bit (...
m90's user avatar
  • 10.1k
26 votes

Approximate Brun's Constant

Python 3, 78 77 75 70 68 62 bytes f=lambda n,k=3,m=1,j=0:k<n and-m%k*j*2/k+f(n,k+2,m*k**4,m%k/k) Thanks to @xnor for golfing off 2 4 bytes and paving the way ...
Dennis's user avatar
  • 210k
26 votes

Is it a weak prime?

Jelly, 7 bytes Æn+Æp>Ḥ Try it online! Explanation ...
PurkkaKoodari's user avatar
25 votes

Calculate the number of primes up to n

C99/C++, 8.9208s (28 Feb 2016) ...
arjan de lumens's user avatar
25 votes

Is it a Mersenne Prime?

05AB1E, 5 bytes A positive number in the form 2n - 1 in binary only consists of 1's. Code: b`¹pP Explanation: ...
Adnan's user avatar
  • 44.3k
25 votes
Accepted

Output the PPCG Prime

Jelly, 55 54 52 47 46 bytes “=÷¡v⁺ʋiṂYR¤"bİɲ}Ñ1Ṇ⁴ẠV⁹yȥGẇ’“¿mŻ“p’Dx39jBo88V There are more convoluted approaches in the revision history, but this simple one ...
Dennis's user avatar
  • 210k
24 votes

Coprimes up to N

Jelly, 4 bytes gRỊT Try it online! How it works ...
Dennis's user avatar
  • 210k
24 votes

The program that will find the next prime number

Mathematica, 9 bytes NextPrime
Greg Martin's user avatar
  • 15.4k
24 votes

​Cuban​ ​Primes

JavaScript (V8), 54 bytes A full program that prints cuban primes forever. for(x=0;;){for(k=N=~(3/4*++x*x);N%++k;);~k||print(-N)} Try it online! NB: Unless you ...
Arnauld's user avatar
  • 191k
22 votes

Primes with a twist

Jelly, 13 bytes “Ŀo‘’FQỌµḟ;¹V Try it online! or run the first ten programs. Background Jelly has several different types of string literals; all of them start ...
Dennis's user avatar
  • 210k
22 votes

Primes with a twist

GS2 (commit 67fea47), 6 3 bytes dnR How it works Like most commands, GS2‘s d is overloaded. Initially, there's an empty list ...
Dennis's user avatar
  • 210k
21 votes

Is this number a prime?

JavaScript, 39 36 bytes Saved 3 bytes thanks to ETHproductions: for(i=n=prompt();n%--i;);alert(1==i) Displays true for a prime, false otherwise. The for loop ...
Hedi's user avatar
  • 1,977
21 votes

Is it a super-prime?

Jelly, 5 bytes ÆRÆNċ Try it online! How it works ...
Dennis's user avatar
  • 210k
21 votes
Accepted

Do I have a prime twin?

Brachylog, 9 8 bytes ṗ∧4√;?+ṗ Try it online! Explanation ...
Fatalize's user avatar
  • 38.5k
20 votes

Find the Smoothest Number

Regex (Perl / PCRE), 66 65 (64🐌) bytes Inspired by seeing that both Martin Ender and jaytea, two regex geniuses, wrote regex solutions to this code golf, I wrote my own from scratch. The famous prime-...
Deadcode's user avatar
  • 11.6k
20 votes

Is this number a prime?

Stack Cats, 62 + 4 = 66 bytes *(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>] Needs to be run ...
Martin Ender's user avatar
20 votes

Is this number a prime?

Brain-Flak, 112 108 bytes ...
Dennis's user avatar
  • 210k

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