Questions tagged [primes]

For challenges about identifying and manipulating prime numbers

Filter by
Sorted by
Tagged with
222
votes
327answers
55k 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 ...
58
votes
106answers
14k 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 ...
23
votes
25answers
3k views

Find the prime factors

In this task, you have to write a program, that computes the prime factors of a number. The input is a natural number 1 < n < 2^32. The output is a list of the prime factors of the number in the ...
60
votes
42answers
13k 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 ...
28
votes
21answers
40k 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 ...
30
votes
38answers
3k 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 ...
30
votes
51answers
5k views

Sum of primes between given range

Write the shortest code for finding the sum of primes between \$a\$ and \$b\$ (inclusive). Input \$a\$ and \$b\$ can be taken from command line or stdin (space seperated) Assume \$1 \le a \le b \le ...
37
votes
4answers
16k views

Fastest semiprime factorization [closed]

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: \$...
22
votes
26answers
10k views

List Prime Numbers [duplicate]

Introduction Prime numbers are simple, right? Well, now you get your chance to find out! Challenge You must write a program or function that takes an input n and ...
51
votes
47answers
8k views

Coprimes up to N

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

Prime factors buddies

Given an integer N > 1, output all other numbers which prime decompositions have the same digits as the prime decomposition of ...
14
votes
8answers
2k views

What is the average of n, the closest prime to n, the square of n and the closest Fibonacci number to n?

This is a math problem which takes quite many things into question, making it rather challenging, and as you might have guessed, it's a code golf, so it should be as short as possible as well. The ...
23
votes
4answers
2k views

Find largest prime which is still a prime after digit deletion

Over at https://math.stackexchange.com/questions/33094/deleting-any-digit-yields-a-prime-is-there-a-name-for-this the following question is asked. How many primes are there that remain prime after you ...
34
votes
11answers
3k 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 ...
21
votes
6answers
3k views

Find the largest fragile prime

Consider the function Remove(n, startIndex, count) that removes count digits from the number ...
72
votes
28answers
7k views

Calculate Phi (not Pi)

No, I don't mean \$\phi = 1.618...\$ and \$π = 3.14159...\$. I mean the functions. \$\phi(x)\$ is the number of integers less than or equal to \$x\$ that are relatively prime to \$x\$. \$π(x)\$ is ...
33
votes
41answers
7k 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 ...
14
votes
7answers
2k views

Is it a prime? w/o math [closed]

Write a program or function in any language that tells if the input is a prime number. The input is a string representing a natural number in base-10. The output is one of the two strings "Prime" or "...
19
votes
38answers
2k views

Recover the power from the prime power

It seems that many people would like to have this, so it's now a sequel to this challenge! Definition: a prime power is a natural number that can be expressed in the form pn where p is a prime and n ...
22
votes
19answers
2k views

Is this a consecutive-prime/constant-exponent number?

A while ago, I had a look at the prime factorization of 27000: 27000 = 23 × 33 × 53 There are two special things about that: consecutive-prime: The primes are consecutive: 2 is the 1st prime, 3 is ...
14
votes
9answers
3k views

Closest 7-Distinct-Prime Product

(via chat) The OEIS entry A123321 lists the sequence of numbers that are the product of seven distinct primes. For brevity, we'll call this a 7DP number. The first few numbers and their corresponding ...
10
votes
18answers
1k views

Find prime factors [duplicate]

A whole program to find the prime factors of a given number. The number will be given on standard input.
7
votes
6answers
2k views

Show Ulam's spiral

Similar to this but in this one you need to write spiral starting from the center where: space means composite number .(dot) means prime number. Size of the ...
17
votes
17answers
1k views

Find the smallest prime from a substring

In 1946 Erdos and Copeland proved that a certain number is a normal number, i.e. the digits in its decimal expansion are uniformly distributed. Users will input a sequence of digits and you will find ...
15
votes
19answers
2k views

Prime Factoral Roots

Inspired by digital roots, the prime factoral root of a number is the number that emerges when you take the prime factors of a number, add them together, and repeat the process on the resulting number,...
8
votes
18answers
1k views

Square-free semiprime counting

Definition A square-free semiprime is a natural number that is the product of two distinct prime numbers. The task Given a natural number n, count all square-free ...
5
votes
7answers
1k views

Return the first N primes

With a twist; your algorithm has to be less complex than O(X2) where X is the Nth prime. Your solution post should include the character count and the theoretical complexity in terms of X (or N, which ...
71
votes
14answers
13k 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 ...
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 ...
36
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 ...
28
votes
2answers
1k views

Can a neural network recognize primes?

Background Recognizing primality seems like a poor fit for (artificial) neural networks. However, the universal approximation theorem states that neural networks can approximate any continuous ...
31
votes
45answers
3k 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 can ...
30
votes
31answers
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 ...
23
votes
25answers
4k views

The Möbius Function

The Möbius Function The Möbius function is an important number theoretic function. Your submission should accept a positive integer n and return the value of the ...
34
votes
14answers
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 ...
20
votes
6answers
2k views

Triangular Ulam spiral

We've had a couple of challenges about the Ulam spiral. But that's not enough. In this challenge we will plot a triangular Ulam spiral (as opposed to the usual, square Ulam spiral). Here's a sketch ...
34
votes
35answers
4k 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 ...
10
votes
7answers
934 views

Golf the pseudoprimes!

Introduction / Background In a recent discussion in the crypto chat I was challenged to discuss / help with the Fermat primality test and Carmichael numbers. This test is based on the premise that <...
39
votes
22answers
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, ...
27
votes
13answers
2k views

Recover the mutated source code

In a very unusual accident involving a small sample of radium, an electrocuted whale, and three gummy bears, some of The Management™'s source code has been mutated. Little does The Management™'s boss ...
26
votes
23answers
3k 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 ...
16
votes
29answers
5k views

The program that will find the next prime number

Intro: You accidentally corrupted the flow of time with a device you made for fun, that turned out to be a time machine. As a result, you got pushed to the far future. You realized that computing, ...
15
votes
21answers
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 ...
14
votes
28answers
1k views

Am I a Sophie Germain prime? [duplicate]

A Sophie Germain Prime is a prime number P such that 2P+1 is prime as well. Given a prime number as input, your task is to determine whether it is a Sophie Germain Prime. Standard Input/Output rules ...
14
votes
34answers
4k views

Generate Sexy Primes

Sexy Primes are pairs of numbers \$(n, n+6)\$ such as \$n\$ and \$n+6\$ are both prime You need to create a function which will take an integer, check for sexy primes from 0 to that integer, and ...
11
votes
13answers
1k views

List all palindromic prime dates between 0000-01-01 and 99999-12-31

You know what a palindrome, a prime and a date are. Your task is to list all dates in 100 thousands of years that fulfill all three characteristics. Nevermind anything but the numbers, use the ...
22
votes
16answers
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 ...
15
votes
36answers
2k views

Recover the prime from the prime power

Definition: a prime power is a natural number that can be expressed in the form pn where p is a prime and n is a natural number. Task: Given a prime power pn > 1, return the prime p. Testcases: <...
13
votes
7answers
382 views

Encode Factor Trees [duplicate]

I once saw on the xkcd fora a format for expressing numbers in an odd way. In this "factor tree" format: The empty string is 1. Concatenation represents multiplication. A number n enclosed in ...
12
votes
17answers
757 views

Divisor sum from prime-power factorisation

The task is to compute the divisor sum of a number given its prime factorisation. Input Two arrays (or something equivalent) of length n, one containing the prime factor and the other containing the ...