Questions tagged [primes]

For challenges about identifying and manipulating prime numbers

Filter by
Sorted by
Tagged with
192
votes
287answers
44k views

Is this number a prime?

Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in ...
72
votes
28answers
6k views

Calculate Phi (not Pi)

No, I don't mean ϕ = 1.618... and π = 3.14159.... I mean the functions. φ(x) is the number of integers less than or equal to <...
69
votes
23answers
3k views

Output the PPCG Prime

This is the PPCG Prime 624 digits long ...
63
votes
13answers
9k views

Calculate the number of primes up to n

π(n) is the number of primes less than or equal to n. Input: a natural number, n. Output: π(n). Scoring: This is a fastest-code challenge. Score will be the sum of times for the score cases. I ...
58
votes
39answers
12k views

Find the Smoothest Number

Your challenge is to find the smoothest number over a given range. In other words, find the number whose greatest prime factor is the smallest. A smooth number is one whose largest prime factor is ...
56
votes
103answers
11k views

List of primes under a million

This is my first code golf question, and a very simple one at that, so I apologise in advance if I may have broken any community guidelines. The task is to print out, in ascending order, all of the ...
50
votes
43answers
5k views

Coprimes up to N

Given a number n >= 2, output all the positive integers less than n where gcd(n, k) == 1 (...
50
votes
18answers
9k views

The prime ant 🐜

The "prime ant" is an obstinate animal that navigates the integers and divides them until there are only primes left! Initially, we have an infinite array A containing all the integers >= 2 : ...
44
votes
22answers
8k views

The prime frog 🐸

The "prime frog" is a strange animal that jumps between integers, until it arrives on 3 or 19... Your program should accept an integer n as input and output the ...
43
votes
12answers
3k views

Prime parity peregrination

The purpose of this challenge is to graphically depict a walk on the plane, where the direction of each step \$k\$ is determined by the primality of \$k\$ and the parity of its binary expansion. ...
42
votes
12answers
5k views

A naturally occurring prime generator

There are quite a large number of prime generating functions. Pretty much all of them are constructed and are based on the sieve of Eratosthenes, the Möbius function or the Wilson's theorem and are ...
41
votes
15answers
5k views

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

Out of all the years I've been making this challenge, 2017 is the first year that's been a prime number. So the question will be about prime numbers and their properties. Your task is to produce a ...
39
votes
13answers
5k views

579085261 is CRAZY, 725582 is GOLF, 10757494 is …?

Your task is to translate a 103-smooth number into an English word, using the method described below. How? Generate the list of prime factors (with repetition) of the input number. Sort the list: ...
38
votes
23answers
3k views

Output the Trinity Hall Prime

Based on this Math.SE question; number copied from this answer. Number originally from a Numberphile video, of course. Your task is to output the following 1350-digit prime number: ...
38
votes
19answers
3k views

Print the nth prime that contains n

This question will be a twist on finding the nth prime number. Challenge You must write a program that will take one input n, ...
37
votes
11answers
5k views

Find the largest prime whose length, sum and product is prime

The number 113 is the first prime whose length 3 is prime, digital sum 5 = 1 + 1 + 3 is ...
37
votes
18answers
3k views

Prime Up your code

Input no input for this challenge The Challenge Write a code that outputs: The first 10 prime numbers whose sum of their digits equal the number of bytes of your code Examples Let's say your ...
36
votes
20answers
5k views

Compute the Carmichael function

Task description In number theory, the Carmichael function λ takes a positive integer n and returns the least positive integer k so that the k-th power of each integer coprime to n equals 1 modulo n. ...
36
votes
17answers
4k views

Primes other than Optimus

Challenge Given an input integer n > 0, output the number of primes (other than n, if n ...
35
votes
34answers
3k views

Is it a Mersenne Prime?

A number is a Mersenne Prime if it is both prime and can be written in the form 2n-1, where n is a positive integer. Your task is to, given any positive integer, determine whether or not it is a ...
35
votes
24answers
3k views

Plus Primes vs Minus Primes

Most of us know... that all primes p>3 are of the form But, how many are the Plus Primes (6n+1) and how many are the ...
34
votes
14answers
1k views

Generate n-ary numbers

A secondary number is a positive integer whose prime factors (without multiplicity) are all less than or equal to its square root. 4 is a secondary number, because ...
34
votes
13answers
2k views

Fond Memories of Past Primes

Consider a prime number p, written in base 10. The memory of p is defined as the number of distinct primes strictly less than p that are contained as substrings of p. Challenge Given a non-negative ...
33
votes
8answers
2k views

No co-prime neighbors

Given a list of positive integers, output whether every adjacent pair of integers in it shares a prime factor. In other words, output truthy if and only if no two neighboring integers in the list are ...
33
votes
17answers
3k views

Smallest Prime with a Twist (A068103)

The task at hand is, given a number n, find the smallest prime that starts with AT LEAST n of the number ...
33
votes
19answers
2k views

Finding The nth Prime such that the prime - 1 is divisible by n

Problem The goal is as the title says to find the nth prime such that the prime - 1 is divisible by n. Explanation Here is an example so you understand the question, this is not necessarily the ...
33
votes
11answers
2k views

Encode an integer

Given positive integer n > 2. We convert it to an array as follows: If it is equal to 2 return an empty array Otherwise ...
32
votes
40answers
5k views

Return the Closest Prime Number

Challenge This is a simple one: Given a positive integer up to 1,000,000, return the closest prime number. If the number itself is prime, then you should return that number; if there are two primes ...
32
votes
14answers
2k views

Array Escape - get out of there

One day you awake only to find yourself caught in an array. You try to just walk out of there, taking one index at the time, but it seems there are other rules: The array is completely filled with ...
32
votes
16answers
2k views

Different ways of defining primes

One of my favorite definitions of the prime numbers goes as follows: 2 is the smallest prime. Numbers larger than 2 are prime if they are not divisible by a smaller prime. However this definition ...
32
votes
6answers
2k views

1, 2, 3, 14… or is it 15?

A well known song by the Irish rock band U2 starts with the singer Bono saying "1, 2, 3, 14" in Spanish ("uno, dos, tres, catorce"). There are various theories as to the significance of those numbers....
30
votes
9answers
3k views

Find Primes in Pi

Primes are everywhere... they hide inside Pi 3.1415926535897932384626433832795028841971693993751 Let's get those primes! The Challenge Given as input an integer ...
30
votes
3answers
5k views

Primality testing formula

Your goal is to determine whether a given number n is prime in the fewest bytes. But, your code must be a single Python 2 expression on numbers consisting of only ...
30
votes
12answers
3k views

That's a prime… almost

If you've ever learned about primes in math class, you've probably have had to, at one point, determine if a number is prime. You've probably messed up while you were still learning them, for example, ...
29
votes
36answers
3k views

Is it a Sphenic Number?

A Sphenic Number is a number that is the product of exactly three distinct primes. The first few Sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114. This is ...
29
votes
3answers
1k views

Stuffing primes in a box

Your task is write a program or function that can fill a given rectangle with prime numbers. The width and height of the ...
28
votes
41answers
2k views

Prime counting function

Introduction The Prime Counting Function, also known as the Pi function \$\pi(x)\$, returns the amount of primes less than or equal to x. Challenge Your program will take an integer x which you ...
28
votes
11answers
2k views

Find the largest gap between good primes

Following the fine tradition of questions such as Find the largest prime whose length, sum and product is prime , this is a variant on a largest prime challenge. Input Your code should not take any ...
28
votes
13answers
3k views

Is it a turtle prime?

As we all know, it's turtles all the way down. But is it primes all the way down too? A number is considered a "turtle-prime" if it satisfies the following conditions: ...
28
votes
12answers
1k views

Prime Divisor Table

Intro Something I've played around with in recreational mathematics has been construction of a divisor table to visually compare/contrast the prime divisors of a set of numbers. The set of input ...
27
votes
33answers
2k views

Calculate the prime factors

We had a prime factorization challenge a while ago, but that challenge is nearly six years old and barely meets our current requirements, so I believe it's time for a new one. Challenge Write a ...
27
votes
42answers
3k views

Sum of primes between given range

Write the shortest code for finding the sum of primes between a and b (inclusive). Input a ...
27
votes
20answers
3k views

Is it a Chen prime?

A number is a Chen prime if it satisfies two conditions: It is prime itself Itself plus two is either a prime or a semi-prime. A prime is a number where it has exactly two divisors and those ...
27
votes
22answers
4k views

Can the number reach 1 by repeatedly subtracting the largest prime less than it?

Challenge: Given a number, take the largest prime strictly less than it, subtract it from this number, do this again to this new number with the biggest prime less than it, and continue doing this ...
27
votes
21answers
32k views

List of first n prime numbers most efficiently and in shortest code [closed]

Rules are simple: First n primes (not primes below n), should be printed to standard output separated by newlines (primes should be generated within the code) primes cannot be generated by an inbuilt ...
27
votes
21answers
1k views

Primenary Strings

A Primenary (binary-prime) string is one which, when written as a binary grid, every row and column has a prime total. That's quite a vague explanation, so let's break it down with a worked example.....
26
votes
22answers
2k views

Is it a weak prime?

A prime is weak if the closest other prime is smaller than it. If there is a tie the prime is not weak. For example 73 is a weak prime because 71 is prime but 75 is composite. Task Write some ...
26
votes
2answers
13k views

Fastest semiprime factorization

Write a program to factorize a semi-prime number in the shortest amount of time. For testing purposes, use this: 38!+1 (523022617466601111760007224100074291200000001) It is equal to: ...
26
votes
21answers
2k views

Smallest n-digit prime containing only these digits

You will need to generate the smallest prime with n digits, and it will only contain digits specified in the list k. Examples: ...
26
votes
8answers
1k views

A083569: Smallest m not occurring earlier such that m+n is prime

Define a 1-indexed sequence as follows: A083569(1) = 1 A083569(n) where n is an integer ...