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.
Programming Praxis 
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]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))A Haskell version.
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(Re my Julia above, a nicer way to count the total number of digits in primes below 2017.)
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]) { add(i,b[j+1]); 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)); } }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));
}
}