Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [primes]

For challenges about identifying and manipulating prime numbers

Filter by
Sorted by
Tagged with
13 votes
12 answers
2k views

Odds for second smallest prime factor

Given a prime number \$p\$ output the asymptotic density of the set of positive integers which have \$p\$ as their second-smallest distinct prime factor Input/Output Input: one of the following ...
Mukundan314's user avatar
10 votes
6 answers
930 views

Unnecessary Fluff

Following the great advice (what do you mean it's not advice?!) on Adding unnecessary fluff we can devise the following task: Take a list of positive integers and a positive integer \$m\$ as input. ...
Command Master's user avatar
8 votes
20 answers
1k views

Piecing Paired Primes

Problem You've stumbled upon a paradoxical mathematical phenomenon related to prime numbers. Consider the following scenario: You have an infinite list of prime numbers: $$2, 3, 5, 7, 11, 13, 17, 19, ....
3.14's user avatar
  • 383
8 votes
8 answers
397 views

Near miss prime multiples

This challenge was originally posted on codidact. Given a number \$n \geq 3\$ as input output the smallest number \$k\$ such that the modular residues of \$k\$ by the first \$n\$ primes is exactly \$\...
Wheat Wizard's user avatar
  • 98.8k
11 votes
12 answers
1k views

The all-high powerful numbers

We've had powerful numbers, yes, but what about highly powerful numbers? Highly powerful numbers Let \$n\$ be a positive integer in the form $$n = p_1^{e_{p_1}(n)}p_2^{e_{p_2}(n)}\cdots p_k^{e_{p_k}(n)...
caird coinheringaahin g's user avatar
7 votes
19 answers
2k views

Number of bits needed to represent the product of the first primes

Input An integer \$n\$ greater than or equal to 1. Output The number of bits in the binary representation of the integer that is the product of the first \$n\$ primes. Example The product of the first ...
Simd's user avatar
  • 2,926
23 votes
31 answers
3k views

Is this a powerful number?

A powerful number is a positive integer \$n\$ such that for every prime \$p\$ that divides \$n\$, \$p^2\$ also divides \$n\$. Or equivalently, \$n\$ is powerful if and only if it can be written in the ...
alephalpha's user avatar
  • 48.2k
-3 votes
7 answers
1k views

Straight pen strokes for Prime Numbers

Challenge You are supposed to output the series I recently designed which goes as follows which are pen stroke counts of ascending prime numbers: ...
Aitzaz Imtiaz's user avatar
14 votes
7 answers
1k views

Gödel encoding - Part II (decoding)

Part I Previous part was considered encoding of non-empty nested lists with a positive integer. Reminding the coding procedure \$G(x)\$: If \$x\$ is a number, \$G(x) = 2^x\$ If \$x\$ is a list \$[n_0,...
lesobrod's user avatar
  • 3,413
31 votes
18 answers
3k views

Gödel encoding - Part I

Related but different. Part II Taken from the book: Marvin Minsky 1967 – Computation: Finite and Infinite Machines, chapter 14. Background As the Gödel proved, it is possible to encode with a unique ...
lesobrod's user avatar
  • 3,413
16 votes
7 answers
2k views

How Super is this Prime?

A super prime is a prime whose index in the list of primes is also a prime: ...
Lecdi's user avatar
  • 1,155
15 votes
19 answers
2k views

Sophie Safe primes

Description Write a program or function that takes in a positive integer \$n\$ as input and outputs all Sophie Germain primes that are safe primes less than or equal to \$n\$. A prime number \$p\$ is ...
Aitzaz Imtiaz's user avatar
15 votes
16 answers
2k views

Imtiaz Germain Primes

Description "Imtiaz Germain primes" is not a technical name in Mathematics, but my weird creation, in the memoir of the famous mathematician Sophie Germain. These primes can be generated by ...
Aitzaz Imtiaz's user avatar
12 votes
18 answers
637 views

Primes with Distinct Prime Digits

There are 18 primes with distinct prime digits (A124674). Namely, they are: \$2, 3, 5, 7, 23, 37, 53, 73, 257, 523, 2357, 2753, 3257, 3527, 5237, 5273, 7253, 7523\$ Your task is to output this ...
Bob th's user avatar
  • 309
5 votes
15 answers
756 views

Shortest code to generate a list of prime numbers within a given range

Strangely never asked before, this question pertains to the generation of a list of prime numbers within a given range using the shortest possible code. Several algorithms, such as the Sieve of ...
Aitzaz Imtiaz's user avatar
15 votes
18 answers
2k views

Distance to the average of the next two prime numbers

Suppose we have a sequence \$P\$. Every element \$P_n\$ represents the distance between the \$n^{th}\$ prime number and the average of the next two prime numbers. For example, \$P_1\$ would be the ...
Trivaxy's user avatar
  • 487
14 votes
14 answers
1k views

n-digit primes given the first m digits

I just discovered this site and this is my first question, I hope I'm doing it correctly. The challenge is the following, you must write a code that prints all the prime numbers of \$n\$ digits. Since ...
Luis Alexandher's user avatar
13 votes
25 answers
999 views

Find the Prime Signature

The Prime Signature of a number is the list of the exponents of the prime factors of a number, sorted in descending order (exponents of 0 are ignored). Inspired by ...
Samathingamajig's user avatar
37 votes
15 answers
3k views

Base Neutral Numbering System

It frustrates me that when you say "base 16", the 16 is in base 10. We need a base neutral way of writing down numbers when favoring a specific base would be inappropriate. How it works We ...
mousetail's user avatar
  • 12.6k
19 votes
13 answers
882 views

As many near-repdigit primes as possible

A near-repdigit number is a positive integer where all the digits are the same, except one. For example 101 and 227 are near-repdigits. A near-repdigit prime is a near-repdigit that is also prime. For ...
user avatar
16 votes
15 answers
2k views

Generate the n'th Fermi-Dirac Prime

A Fermi-Dirac Prime is a prime power of the form \$p^{2^k}\$, where \$p\$ is prime and \$k \geq 0\$, or in other words, a prime to the power of an integer power of two. They are listed as integer ...
infinitezero's user avatar
  • 1,646
13 votes
22 answers
1k views

Even and Odd kinds

Let \$n\$ be some positive integer. We say that \$n\$ is of even kind if the prime factorisation of \$n\$ (counting duplicates) has an even number of integers. For example, \$6 = 2 \times 3\$ is of ...
caird coinheringaahin g's user avatar
12 votes
20 answers
2k views

Prime number checksum

Given a message, append checksum digits using prime numbers as weights. A checksum digit is used as an error-detection method. Take, for instance, the error-detection method of the EAN-13 code: The ...
math scat's user avatar
  • 9,378
12 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 ...
The Thonnu's user avatar
  • 18.1k
6 votes
3 answers
570 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 ...
Aiden4's user avatar
  • 2,465
22 votes
12 answers
3k 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. ...
AZTECCO's user avatar
  • 10.8k
18 votes
16 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 ...
pajonk's user avatar
  • 16.4k
8 votes
7 answers
680 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 ...
DialFrost's user avatar
  • 5,079
16 votes
2 answers
887 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: ...
AnttiP's user avatar
  • 7,898
17 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 ...
drmosley's user avatar
  • 757
12 votes
6 answers
1k 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 ...
xiver77's user avatar
  • 2,365
6 votes
2 answers
840 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 ...
xiver77's user avatar
  • 2,365
10 votes
10 answers
583 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 ...
caird coinheringaahin g's user avatar
14 votes
4 answers
605 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 ...
AnttiP's user avatar
  • 7,898
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 = ...
Ha'Penny's user avatar
  • 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 ...
caird coinheringaahin g's user avatar
26 votes
7 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 ...
AndrewTheCodegolfer's user avatar
1 vote
1 answer
224 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 ...
David Roonie's 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 ...
caird coinheringaahin g's user avatar
16 votes
15 answers
892 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
821 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 =...
SegFaultPlus4's user avatar
0 votes
4 answers
204 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 ...
Rydwolf Programs's user avatar
22 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, ...
pxeger's user avatar
  • 23.8k
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 ...
Beefster's user avatar
  • 9,951
26 votes
25 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). ...
caird coinheringaahin g's user avatar
7 votes
10 answers
958 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 ...
l4m2's user avatar
  • 24.4k
8 votes
6 answers
689 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 ...
Manish Kundu's user avatar
  • 5,270
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\$ ...
caird coinheringaahin g's 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 ...
caird coinheringaahin g's user avatar
-4 votes
1 answer
240 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 (...
user101295's user avatar

1
2 3 4 5
7