## Prime String

### January 10, 2017

Today’s exercise is easy to describe, but has some tricky edge cases that make it hard to implement:

Given a string of the prime numbers appended sequentially — 2357111317192…. — and an index n, return the string of five digits beginning at index n. For instance, the five characters starting at index n = 50 are 03107. The first 61 characters of the prime string are shown below:

```0         1         2         3         4         5         6
0123456789012345678901234567890123456789012345678901234567890

2357111317192329313741434753596167717379838997101103107109113```

Your task is to write a program to find the substring of the string of all primes starting at the nth character. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 7 Responses to “Prime String”

1. Paul said

In Python. primegen is a lazy prime generator.

```def prime_str(n):
primes = primegen()
res = ""
while len(res) < 5:
strp = str(next(primes))
L = len(strp)
if L >= n:
res += strp[n:n+5]
n = max(0, n-L)
return res[:5]
```
2. Jussi Piitulainen said

Decoupling digit generation from slice selection, in Python.

```from itertools import islice

def prime_digits():
for p in primegen():
yield from str(p)

def prime_str(k, n):
return ''.join(islice(prime_digits(), k, k + n))
```
3. Globules said

```import Math.NumberTheory.Primes.Sieve (primes)

digits :: String
digits = concatMap show primes

fiveAt :: Int -> String
fiveAt n = take 5 \$ drop n digits

main :: IO ()
main = do
putStrLn \$ fiveAt 50
putStrLn \$ fiveAt 12345678
```
```\$ ./primestr
03107
24126
```
4. Jussi Piitulainen said

This is Julia 0.5, with its new generator expressions. I didn’t find an unbounded prime generator (one could be written) so I just fake it with a sufficiently large pool of primes, which is readily available. Julia’s iteration protocol is similar to but different from that of Python, ISWIM. In particular, the value of a generator expression does not itself have state.

```module Play

using Primes
pool = primes(3000)

digits(source) = (c for p in source for c in string(p))

function example(gen)
println(join(take(drop(gen, 0), 3)))
println(join(take(drop(gen, 3), 3)))
println(join(take(drop(gen, 3), 0)))
end

example(digits(pool))
# prints:
# 235
# 711
#

before = length(join(digits((p for p in pool if p < 2017))))
present(gen) = println(join(take(drop(gen, before), 4)))

present(digits(pool))
# prints:
# 2017

end
```
5. Jussi Piitulainen said

(Re my Julia above, a nicer way to count the total number of digits in primes below 2017.)

```before = sum(length(string(p)) for p in pool if p < 2017)
```
6. matthew said

Here’s some JS using the new ES6 generators. This one only starts building up the string once the first required prime is reached, before that it just keep a character count for the primes seen. Uses a simple incremental sieve of Eratosthenes – not the most efficient, but does the job.

```"use strict"
function primestring(n,m) {
let len = 1, nextlen = 10, total = 0;
let primegen = primes(), s = null;
for (const p of primegen) {
if (p >= nextlen) {
nextlen *= 10; len++;
}
total += len;
if (total > n) {
s = String(p).substring(n-total+len,len);
break;
}
}
for (const p of primegen) {
s += String(p);
if (s.length >= m) {
return s.substring(0,m);
}
}
}

function* primes() {
let a = []; // 3,5,7,9,...
let b = []; // new primes to be inserted
const add = (n,p) => {
if (!a[n]) a[n] = [];
a[n].push(p);
}
yield 2;
for (let i = 1, j = 0; ; i++) {
if (i == b[j]) {
j += 2;
}
if (a[i]) {
for (const p of a[i]) add(i+p,p);
} else {
b.push(2*i*(i+1),2*i+1);
yield 2*i+1;
}
}
}

// Naive implementation for comparison
function primestring0(n,m) {
let s = "";
for (const p of primes()) {
s += p;
if (s.length >= n+m) break;
}
return s.substring(n,n+m);
}

console.log(primestring(0,55));
console.log(primestring(50,5));

for (let i = 0; i < 100; i++) {
for (let j = 0; j < 20; j++) {
console.assert(primestring0(i,j) == primestring(i,j));
}
}
```
7. Anhy said

package prime.string;
import static java.lang.System.out;
import java.util.Scanner;
public class PrimeString {
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
out.print(“Enter the index: “);
int index = keyboard.nextInt();
out.println();
int a = 2;
String b = “”;
while(b.length() < index+5)
{
if(a % 2 != 0 && a % 3 != 0 && a % 5 != 0 && a % 7 != 0 || (a == 2 || a == 3 || a == 5 || a == 7))
{
b += a;
}
a++;
}
System.out.println(b.substring(index,index+5));
}
}