2022 Developer Survey is open! Take survey.

Questions tagged [primes]

For challenges about identifying and manipulating prime numbers

Filter by
Sorted by
Tagged with
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. ...
user avatar
  • 9,426
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 ...
user avatar
  • 10.8k
8 votes
7 answers
490 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 ...
user avatar
  • 3,031
16 votes
2 answers
787 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: ...
user avatar
  • 6,645
19 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 ...
user avatar
  • 757
11 votes
6 answers
851 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 ...
user avatar
  • 2,121
6 votes
2 answers
452 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 ...
user avatar
  • 2,121
10 votes
10 answers
554 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 ...
user avatar
14 votes
4 answers
439 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 ...
user avatar
  • 6,645
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 = ...
user avatar
  • 193
26 votes
13 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 ...
user avatar
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 ...
user avatar
1 vote
1 answer
177 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 ...
user avatar
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 ...
user avatar
16 votes
15 answers
841 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\$. ...
user avatar
12 votes
7 answers
771 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 =...
user avatar
0 votes
4 answers
158 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 ...
user avatar
21 votes
20 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, ...
user avatar
  • 18.4k
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 ...
user avatar
  • 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). ...
user avatar
7 votes
10 answers
928 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 ...
user avatar
  • 12.7k
8 votes
6 answers
683 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 ...
user avatar
  • 4,910
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\$ ...
user avatar
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 ...
user avatar
-3 votes
1 answer
180 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 (...
user avatar
47 votes
24 answers
4k views

Ginormous number

Output this 1364-digit base-10 number: ...
user avatar
  • 137k
7 votes
15 answers
865 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 3,585
32 votes
7 answers
4k views

Shortest "arithmetic" formula to output 1000 primes

Write a formula using only the digits 0-9, +, *, -, <...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,886
21 votes
27 answers
2k views

Prime Power Switch

Input: A positive integer n=p^q where p and q are prime. Output: Output the result of ...
user avatar
  • 1,345
-3 votes
5 answers
190 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 ...
user avatar
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 ...
user avatar
  • 1,345
6 votes
16 answers
773 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? ...
user avatar
  • 23.1k
20 votes
9 answers
645 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)\$...
user avatar
  • 23.1k
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 ...
user avatar
  • 1,979
13 votes
10 answers
908 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 ...
user avatar
  • 6,449
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 ...
user avatar
7 votes
10 answers
888 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. ...
user avatar
-9 votes
26 answers
392 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 ...
user avatar
  • 179
3 votes
3 answers
348 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^...
user avatar
9 votes
2 answers
419 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 ...
user avatar
  • 115
17 votes
1 answer
657 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 ...
user avatar
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. ...
user avatar
15 votes
11 answers
2k 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, ...
user avatar
  • 159
5 votes
13 answers
456 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. ...
user avatar
  • 3,704
25 votes
21 answers
2k views

Some Prime Peerage

(Randomly inspired by https://mathoverflow.net/q/339890) (Related: 1, 2) Given an input list of distinct prime numbers (e.g., [2, 5, 7]), and a integer ...
user avatar
  • 42.8k
29 votes
18 answers
4k views

Infinitely many primes

Since Euclid, we have known that there are infinitely many primes. The argument is by contradiction: If there are only finitely many, let's say \$p_1,p_2,...,p_n\$, then surely \$m:=p_1\cdot p_2\cdot.....
user avatar
  • 43k

1
2 3 4 5
7