Questions tagged [primes]

For challenges about identifying and manipulating prime numbers

Filter by
Sorted by
Tagged with
11 votes
18 answers
1k views

Find the nth Mersenne Prime

A number is a Mersenne Prime if it is both prime and can be written in the form 2m-1, where m is a positive integer. For example: 7 is a Mersenne Prime because it is 23-1 11 is not a Mersenne Prime ...
7 votes
2 answers
418 views

Generate Fibonacci Primes Quickly

Unsurprisingly, fibonacci primes are primes that are also Fibonacci numbers. There are currently 34 known Fibonacci primes and an additional 15 probable Fibonacci primes. For the purpose of this ...
  • 2,215
22 votes
12 answers
2k views

How many Sieve of Eratosthenes hits?

Sieve of Eratosthenes is a method for finding prime numbers: take the sequence of all positive integer numbers starting from 2 then for each remaining number drop all its multiples. ...
  • 9,836
18 votes
15 answers
1k views

Long period primes

A long period prime is a prime number \$p\$ such that decimal expansion of \$1/p\$ has period of length \$(p-1)\$. Your task is to output this number sequence. For purposes of this challenge we will ...
  • 12.3k
8 votes
7 answers
534 views

Factorials of primes decomposition

You have to decompose a positive integer/fraction as a product of powers of factorials of prime numbers. For example ...
  • 3,049
16 votes
2 answers
820 views

Golf the prime numbers in Shue

I'd like to introduce a new? programming language I call Shue (Simplified Thue). It has very simple syntax. Here is a program that checks if an input is divisible by three: ...
  • 6,775
18 votes
27 answers
2k views

Prime a*b+c of N

Given an integer \$N\$, print or return integers \$a\$, \$b\$, and \$c\$ that satisfy all of the following conditions, if such integers exist: \$a \times b + c = N\$ \$a\$, \$b\$, and \$c\$ are all ...
  • 727
11 votes
6 answers
946 views

High throughput prime numbers

This challenge is inspired by the High throughput Fizz Buzz challenge. The goal Generate a list of prime numbers up to 10,000,000,000,000,000. The output of primes should be in decimal digits followed ...
  • 2,273
6 votes
2 answers
486 views

Write the most optimized assembly program to detect a prime number (from a bigger range!)

This is the second version of the task. The original task had a defect that the given range of integers was too small. This was pointed out by @harold that other methods couldn't defeat the way of ...
  • 2,273
10 votes
10 answers
560 views

Primes dividing consecutive composites

Grimm's conjecture states that, for any set of consecutive composite numbers \$n+1, n+2, ..., n+k\$, there exist \$k\$ distinct primes \$p_i\$, such that \$p_i\$ divides \$n+i\$ for each \$1 \le i \le ...
14 votes
4 answers
471 views

The Most Wanted Prime Numbers

Output a sequence of all the primes that are of the following form: 123...91011...(n-1)n(n-1)..11109...321. That is, ascending decimal numbers up to some ...
  • 6,775
16 votes
15 answers
2k views

Print Gobar Primes

Gobar primes (A347476) are numbers which give a prime number when 0's and 1's are interchanged in their binary representation. For example, \$10 = 1010_2\$, and if we flip the bits, we get \$0101_2 = ...
  • 193
30 votes
14 answers
2k views

Is it a Giuga number?

Giuga numbers (A007850) are composite numbers \$n\$ such that, for each prime factor \$p_i\$ of \$n\$, \$p_i \mid \left( \frac n {p_i} -1 \right)\$. That is, that for each prime factor \$p_i\$, you ...
20 votes
6 answers
2k views

Recognize most smaller primes with a regex

This time, you are working on a regex. Your regex is meant to approximately full-match the base-10 representations of primes \$0 \le p < 1000\$, while ignoring any non-numeric string or composite ...
1 vote
1 answer
178 views

No of subsets of a given array such that their product is in the form of p1*p2*p3 [closed]

Given an array \$A\$ of size \$n\$. You have to find the number of subsets such that their product is in the form of \$p_1 \times p_2 \times p_3 \dots\$ where \$p_1, p_2, p_3, \dots\$ are prime ...
23 votes
17 answers
2k views

Reconstruct a recursively prime-encoded integer

Recursively prime-encoded integers Consider \$11681169775023850 = 2 \times 5 \times 5 \times 42239 \times 5530987843\$. This isn't a nice prime factorisation, as \$42239\$ and \$5530987843\$ make it ...
16 votes
15 answers
848 views

Outputting Blum Integers

According to Wikipedia, In mathematics, a natural number \$n\$ is a Blum integer if \$n = p \times q\$ is a semiprime for which \$p\$ and \$q\$ are distinct prime numbers congruent to \$3 \bmod 4\$. ...
's user avatar
12 votes
7 answers
778 views

Prime Factorization - but on the exponents too

Though there is a prime factorization challenge and it's here, this, I feel, will be a bit more interesting than that one. To understand this, let's have an example; I will use 5,184 for this. \$5184 =...
0 votes
4 answers
169 views

Prime Factorization [duplicate]

Although there was a prime factors challenge posted ten years ago, it has tedious I/O and restricted time. In this challenge, your task is to write a program or function which takes an integer \$n \ge ...
21 votes
21 answers
3k views

Gödel numbering of a string

Background Gödel numbers are a way of encoding any string with a unique positive integer, using prime factorisations: First, each symbol in the alphabet is assigned a predetermined integer code. Then, ...
  • 22.6k
22 votes
22 answers
1k views

Make it prime with the smallest suffix

Given a positive integer as input, output the smallest positive integer such that appending its digits (in base 10) to the end of the input number will form a prime number. Examples ...
  • 9,791
24 votes
19 answers
1k views

Calculate Home Primes

The Home Prime of an integer \$n\$ is the value obtained by repeatedly factoring and concatenating \$n\$'s prime factors (in ascending order, including repeats) until reaching a fixed point (a prime). ...
7 votes
10 answers
931 views

Random pair of primes

Given a positive input \$n\$, output a random pair of primes whose difference is \$n\$. It's fine if there's another prime between them. Every pair should possibly appear and the program should have ...
  • 13k
8 votes
6 answers
684 views

Finding Distant Primes

Let us call a prime \$p\$ an \$(m,k)\$-distant prime \$(m \ge 0, k \ge 1, m,k \in\mathbb{Z})\$ if there exists a power of \$k\$, say \$k^x (x \ge 0, x \in\mathbb{Z})\$, such that \$|k^x-p| = m. \$ For ...
  • 4,940
13 votes
4 answers
1k views

I ain't no Fortunate sum

The primorial \$p_n\#\$ is the product of the first \$n\$ primes. The sequence begins \$2, 6, 30, 210, 2310\$. A Fortunate number, \$F_n\$, is the smallest integer \$m > 1\$ such that \$p_n\# + m\$ ...
24 votes
27 answers
2k views

Reconstruct an integer from its prime exponents

All integers \$n > 0\$ can be expressed in the form $$n = \prod_{\text{prime } p} p^e = 2^{e_2} 3^{e_3} 5^{e_5} 7^{e_7} \cdots$$ This form is also known as it's prime factorisation or prime ...
-3 votes
1 answer
198 views

Python Prime Problem [duplicate]

Your challenge is to write a Python program to print all the primes (separated by whitespace) less than a given integer N with an asterisk (...
47 votes
24 answers
5k views

Ginormous number

Output this 1364-digit base-10 number: ...
  • 139k
7 votes
15 answers
881 views

Prime generating function

Background The Python code ((((((((n%35)^11)*195)|53)&181)+n)%168)*n)+83 produces 74 distinct primes for \$0 \le n \le 73\$. This code also works in Java. The ...
18 votes
13 answers
1k views

All-inclusive semi-primes

\$723 = 3 \times 241\$ is a semi-prime (the product of two primes) whose prime factors include all digits from \$1\$ to \$n\$, where \$n\$ is the total number of digits between them. Another way to ...
32 votes
20 answers
3k views

Looks prime to me!

Figuring out whether a given number is prime, while not very complicated, is kind of hard. But making a guess doesn't need to be. Seeing whether a number is a multiple of 2 or 5 is easy - you can just ...
  • 3,615
32 votes
7 answers
4k views

Shortest "arithmetic" formula to output 1000 primes

Write a formula using only the digits 0-9, +, *, -, <...
23 votes
16 answers
2k views

Delicate primes

Inspired by Find the largest fragile prime. By removing at least 1 digit from a positive integer, we can get a different non-negative integer. Note that this is different to the ...
16 votes
21 answers
1k views

Double Prime Words

Consider a word/string of length \$n\$, only including the letters A-Z, a-z. A word/string is a double prime word if and only if n is prime and the sum of the letters, s, is also prime, using their ...
  • 1,896
23 votes
28 answers
2k views

Prime Power Switch

Input: A positive integer n=p^q where p and q are prime. Output: Output the result of ...
  • 1,365
-3 votes
5 answers
194 views

Prime decimal representations of prime binary numbers [duplicate]

Problem Statement: Consider a number n in base-10. Find the smallest base-10 integer i greater than ...
31 votes
31 answers
5k views

Is it almost-prime?

Sandbox Definition: A positive integer n is almost-prime, if it can be written in the form n=p^k where ...
  • 1,365
6 votes
17 answers
863 views

Prime Challenge

CODE GOLF & Coding Challenges: In today's challenge, you'll be asked to print the following very special AND tricky AND satisfying Prime Number...! Are you golfers ready? ...
  • 23.3k
20 votes
9 answers
650 views

Prime Modified Z-Factorials

Let me explain one by one the above terms... We will call \$\text{Z-Factorial}(n)\$ of a positive integer \$n\$, \$n!\$ (i.e. \$n\$ factorial) without any trailing zeros. So, \$\text{Z-Factorial}(30)\$...
  • 23.3k
28 votes
19 answers
3k views

Legendre's (Unsolved) Conjecture

Legendre's Conjecture is an unproven statement regarding the distribution of prime numbers; it asserts there is at least one prime number in the interval \$(n^2,(n+1)^2)\$ for all natural \$n\$. The ...
  • 2,009
13 votes
10 answers
912 views

Find all Belphegor primes

A Belphegor number is a number of the form \$(10^{n+3}+666)*10^{n+1}+1\$ (1{n zeroes}666{n zeroes}1) where \$n\$ is an non-negative integer. A Belphegor prime is a ...
  • 6,749
16 votes
7 answers
1k views

Generate *all* coprime tuples

Given integers k and n, generate a sequence of n unique k-tuples of pairwise coprime ...
7 votes
10 answers
890 views

Draw the prime race tracks

Odd prime numbers are either in the form of 4k+1 or 4k+3 where k is a non-negative integer. ...
-9 votes
26 answers
401 views

Produce all even primes

A prime number is a positive integer that has exactly two divisors 1 and the number itself. For example number 7 is a prime since it is divisible by 1 and 7. Number 1 is not a prime since it has only ...
  • 179
3 votes
3 answers
350 views

Generate A298757 [closed]

Miller-Rabin test Given a base \$b\$ and an odd number \$n\$: Write \$n\$ as \$2^{s}\times d + 1\$ where \$d\$ is odd \$n\$ is a strong probable prime if either: \$b^d\equiv 1 \pmod n\$ \$b^{d\cdot2^...
's user avatar
9 votes
2 answers
424 views

Find the largest recurring prime

Inspired by Find the largest fragile prime A recurring prime (or whatever you choose to call it) is a prime that, when removing leading digits, always remain prime regardless of how many digits are ...
  • 115
17 votes
1 answer
669 views

Is this ordinal prime?

You are given an countable ordinal \$1 < r < \varepsilon_0\$. Determine whether or not it is prime. If not, provide exactly two ordinals \$r_0, r_1 < r\$ such that \$r_0r_1 = r\$, following ...
31 votes
5 answers
2k views

Longest Prime Sums

Sandbox There are special sets S of primes such that \$\sum\limits_{p\in S}\frac1{p-1}=1\$. In this challenge, your goal is to find the largest possible set of primes that satisfies this condition. ...
15 votes
11 answers
3k views

Letters associated with prime numbers

If we assign each letter a respective integer, starting from 1, then a is 1, b is 2, c is 3, and so on. After z, the letters loop back around, but with a in front (aa, ab, ac). It then goes to ba, bb, ...
  • 159
5 votes
13 answers
457 views

Please Read Primes

Do you know the book Murderous Maths, in the Horrible Science series? In the book, the Laplace Princess' "ridiculous" cipher might be interesting enough and simple enough to be a code-golf challenge. ...
  • 3,826

1
2 3 4 5
7