[Challenge] Prime Number Printer

oduffy · June 7, 2017, 5:06pm

#Code Challenge #9: June 7, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Facebook:

###Basic Difficulty

Write a function, primeNumberDetector, that tests if a number, n is a prime number.

Function Name: primeNumberDetector
Input: integer n
Output: boolean: true if n is a prime number else false.
Example: primeNumberDetector(13) => True

#####Find out more about basic challenges.

###Intermediate difficulty

Write a function, primeNumberPrinter, that will print out all prime numbers in a given string.

Function Name: primeNumberPrinter
Input: A single string
Output: An integer array of the prime numbers contained in the string
Example: primeNumberPrinter("abc2134kd31"), will output an array [2,13,3,3,31] (in the order they appear in the string).

#####Find out more about intermediate challenges.

###Hard Difficulty

Write primeNumberDetector and primeNumberPrinter as efficiently as possible.

#####Find out more about hard challenges and Big O

`Reply` to this thread with a link to your code on repl.it to participate! Don’t just submit your code, remember to `explain` your solution, too! If you want to be considered as the winner, your function `must` have the `correct name` and provide `output in the format specified` above, you also need to abide by our other simple rules.

The fine print:

Click the links to find out more about:

the rules & how to participate in challenges
how challenges are used as job interview questions
why Codecademy runs challenges (and why they are formatted this way)
more details about the challenges and why we think they are useful.
find previous challenges (and see the past winners) in our Challenge Index

fredswed · June 7, 2017, 5:56pm

Basic level: I am glad I found the for - else loop

https://repl.it/IaxT/4

byteslayer90131 · June 7, 2017, 6:59pm

Here’s my take on the basic difficulty, I’ll work on the intermediate difficulty next

https://repl.it/IbDg/7

micromaster15787 · June 7, 2017, 9:36pm

Basic level

With a small and limited number of relevant primes, the most efficient (at least in time) is to look up the candidate number in a list.

https://repl.it/IbRg/1

def primeNumberDetector(n):
    return n in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,  \
        53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, \
        109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, \
        181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, \
        257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, \
        337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, \
        419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, \
        491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, \
        587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, \
        659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, \
        751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, \
        839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, \
        937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

Intermediate level

This is a question of hacking out the relevant strings. Str.isdigit() is an interesting built-in method, and seems to perform exactly the job required: true if all the chars are digits and false otherwise. A couple of nested for-loops will find the numbers, and a simple look up selects the primes.

Edit

Thanks to danieloduffy who pointed out that at this level primes are not limited to three digits. Thus I have put in an unlimited length prime detector, using a quick search for all multiples of 2,3 or 5, and then doing successive divisions for numbers above 30. The optimisation comes from checking two in every 6 possible divisors (see wikipedia) — although it’s still O(n) it’s quicker than checking every two.

https://repl.it/IbP7/4

import math

def primeNumberDetector(n):
    if n < 2:
        return False
    elif n < 4:
        # 2 and 3 are prime
        return True
    elif (n % 6) in (0,2,3,4):
        # must be divisible by 2 or 3
        return False
    else:
        limit = int(math.sqrt(n))+1
        for i in range(5,limit,6):
            if n % i == 0 or n % (i + 2) == 0:
                return False
        return True



def primeNumberPrinter(text):

    # collect candidate numbers
    nums = []
    # walk along the original string
    for start in range(len(text)):
        # extend possible string one char at a time
        for end in range(start + 1, len(text) + 1):
            if text[start:end].isdigit():
                # if it's a valid number
                a = int(text[start:end])
                # see if it's a prime: if so, remember it
                if primeNumberDetector(a): 
                    nums.append(a)
            else:
                # short circuit as soon as end gets to end of string 
                # or it's no longer a digit
                break

    # return the list of primes
    return nums

By the way, how do you paste a working embedded repl.it on this blog?

Never mind, figured it out. Sometimes knowing Markdown is more of a hindrance than a help!

Tim F

geenium · June 7, 2017, 10:05pm

Here’s my solution for the basic difficulty
https://repl.it/IbUm/1

mtf · June 7, 2017, 10:18pm

Basic Difficulty in JS

var sieve = new Array(1001);
var j, i = 1001, p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
while (i-- > 2) {
    sieve[i] = 1;
}
sieve[0] = 0;
sieve[1] = 0;
for (i = 0; i < p.length; i++) {
    j = p[i];
    k = j;
    while (j + k < 1001) {
        j += k;
        sieve[j] = 0;        
    }
}

function primeNumberDetector(x) {
  if (isNaN(x)) {
    return "Type Error";
  } else if (x < 0 || x > 999) {
    return "Range Error";
  } else if (parseInt(x) !== x) {
    return "Value Error";
  }
  return !!sieve[x];
}

console.log(primeNumberDetector('x'))
console.log(primeNumberDetector(1089))
console.log(primeNumberDetector(99.7))
console.log(primeNumberDetector(99))
console.log(primeNumberDetector(997))

https://repl.it/IbWe/1

The function only needs a base of primes up to the square root of a 1000. The sieve poplulates an array with 1’s then replaces values at non-prime indices with a 0.

!!sieve[x]

converts the result to a boolean.

Edit: Added some error checking.

tomegz · June 7, 2017, 10:35pm

Hard/Intermediate
Javascript - ES6
Edit: fix indentation
Edit 2: push integers into result array instead of strings

https://repl.it/IbWw/3

To achieve good time complexity, the function only checks for mathematically possible divisors of a number which happens to be square root of a given number.

My thinking behind the main function was to loop through every character in a given sentence and:

create possiblePrime which is substring of our input. When the loop reaches a letter instead of a number the possiblePrime is an empty string again so a string like “3skao1” will not count “31” as correct.
when loop reaches a number it pushes it as a result if its a prime and then checks if our possiblePrime substring contains prime numbers to push also, so in my second example “abc2137kd31” you can see how it catches 2137, 137, 37, 7 - they are all prime numbers.

oduffy · June 7, 2017, 10:42pm

For the intermediate solution, we didn’t say you can presume or only test for primes below 1000!

sheemo · June 8, 2017, 3:01am

https://repl.it/Ibi0

    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0 or n < 2:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

def primeNumberPrinter(s):
    primes = []
    for i in range(len(s)):
        temp = ""
        while i != len(s) and ord(s[i]) <= 57 and ord(s[i]) >= 48:
            temp += s[i]
            if primeNumberDetector(int(temp)):
                primes.append(int(temp))
            i += 1
    print(primes)

print(primeNumberDetector(17))
print(primeNumberDetector(1))
print(primeNumberDetector(982451653))
primeNumberPrinter("23571317")

Hard submission by Sheemo in Python3:
This is an implementation of the AKS Primality Test, which recognizes that primes are usually of the form 6k + 1 or 6k - 1, except for 2 and 3. Hence, the tests checks divisors of this form. The primeNumberPrinter would determine if the value s[i] is a number, add it to temp, then use the primeNumberDetector (good code reuse!) to determine if it is a prime.

mtf · June 8, 2017, 4:04am

Sorry for the extra clutter. This shouldn’t count as a submission. After giving a closer look at the algorithm it became evident a way to provide the program with primes from the generated data which serves in the building of the sieve. I’m sure still further refiements are possible and cannot be sure how far this would extend, but in theory, it appears sound.

var limit = 999;
var i = limit + 1, j, k = 0, u = i;
var sieve = new Array(i);
while (i-- > 2) {
    sieve[i] = 1;
}
sieve[0] = 0;
sieve[1] = 0;
do {
    j = nextPrime(k);
    k = j;
    while (j + k < u) {
        j += k;
        sieve[j] = 0;
    }
} while (k < Math.sqrt(u));

function nextPrime(n) {
  while (!sieve[++n]) {
    continue;
  }
  return n;
}

function primeNumberDetector(x) {
  if (isNaN(x)) {
    return "Type Error";
  } else if (x < 0 || x > limit) {
    return "Range Error";
  } else if (parseInt(x) !== x) {
    return "Value Error";
  }
  return !!sieve[x];
}

console.log(primeNumberDetector('x'))
console.log(primeNumberDetector(1089))
console.log(primeNumberDetector(99.7))
console.log(primeNumberDetector(99))
console.log(primeNumberDetector(997))

https://repl.it/IbWe/3

By the Fundamental theorem of arithmetic, every number that is not a prime is the multiple of one or more primes. That is the engine behind this sieve, which idea goes back a couple millenium and then some.

Edit:

The limit, is a variable I’ve thrown in, in preparation for the intermediate challenge.

shrinkhla · June 8, 2017, 4:43am

Basic difficulty in Java
https://repl.it/Ibk5/20

b-twin · June 8, 2017, 11:18am

My submission for basic and intermediate challenge as one code because the intermediate function uses the basic one. The challenge definition doesn’t precise what is the most “efficient” solution; should speed be the only factor, the primeNumberDetector function should be implemented using a sieve. As these are horrible memory hogs though, I opted for a simple trial division that finishes almost immediately for primes up to 14 digits long. Hopefully this awareness qualifies my code for hard challenge as well.

The primeNumberPrinter function takes advantage of the trial division prime-checker as well as 2 other helper functions:

combs(text) - to find numbers as combinations of digits in order they appear in the string:

>>> combs("123")
(1, 12, 123, 2, 23, 3)

I’ve been unsuccessfully trying to code this one for the previous challenge but dropped it here with next to no effort, possibly thanks to the fact it started as something else It is also more efficient than itertools.combinations as it doesn’t consider unnecessary permutations.

isnumber(character) - to identify digits. As again, the challenge definition doesn’t precise what “digit” characters the input string may feature and what to do with them, I took the liberty to limit detection to [0-9] from ASCII set using my own function to avoid issues with unicode characters in built-in string methods in Python.

Now, the primeNumberPrinter function iterates through the string, identifying numbers as series of digits separated with strings of non-digit characters. Eveytime it finds a digit after a non-digit, it stores the index in nx ; everytime it finds a non-digit after a digit, it recognizes it as the end of the series, slices the number out of the string and stores in nums array (this is something I’d normally do it with regexp, but single iteration with splicing is likely faster and still quite compact - props to Factoradic for feedback in the anagram challenge that made me aware of it!). Once the iteration is complete, numbers are sent to combs function, and its result is filtered with primeNumberDetector to output primes only - this is done in-place using list comprehension for best efficiency.

Because the prime-checking is done with a function, I made no adjustments for repeating numbers - Python uses memoization to cache computation of those.

The solution is flexible, allowing for replacing the isnumber function with one that converts or rejects some of the non-ASCII decimals. Also the prime finder could be replaced with a sieve should more constrained challenge conditions deem it necessary.

def primeNumberDetector(n):
    if n == 2: return True
    if n in [0,1] or (n % 2) == 0: return False    
    maxprime = int(n**(0.5))+1

    for i in range(3, maxprime, 2):
        if (n % i) == 0: return False

    return True

def combs(text):
    comblist = []
    text = str(text)
    tl = len(text)
    for i in range(tl):
        j = 1
        while i + j <= tl: 
            comblist.append(int(text[i:i+j]))
            j += 1
    return tuple(comblist)

def isnumber(x):
    return x in "0123456789"
    
def primeNumberPrinter(text):
    text = "-" + text + "-" # start and end string with nondigits to 
    nums = []               # keep boundaries logic below simple
    nx = 0          # nx holds index of begin of each digit series
    for i in range(len(text)):
        if isnumber(text[i]) and not nx:   # nondigit/digit boundary
            nx = i
        elif not isnumber(text[i]) and nx: # digit/nondigit boundary
            nums.append(text[nx:i])
            nx = 0
    return [x for i in nums for x in combs(i) if primeNumberDetector(x)]

https://repl.it/IcIk/1 - not embedding because this page becomes a nightmare to navigate when everyone does it.

byteslayer90131 · June 8, 2017, 1:16pm

so there’s no restrictions to the number of digits for each possible prime number?

cloudrunner15916 · June 8, 2017, 7:33pm

Here is my Python 3 submission for “Basic Difficulty”.

It requires the initialization of a set, with the first eleven primes and calculation of their product.
First I check if the number belongs to the set of eleven. If so, then we are done.
Otherwise, I check if the number and the product of the first eleven
are relatively prime, i.e. have a “greatest common factor” of one.
If so, then the number is a prime number, else, it is not.

Here is a link to my code:

https://repl.it/IdEb/1

z3r0_c00l · June 9, 2017, 1:00pm

My submission for the basic challenge. The basic thought was to do as much error checking or simple math prior to getting into iterations to cut down on overhead.

https://repl.it/Ida4/17

function primeNumberDetector (n){
	
	// Tests to make sure n is an integer greater than 0
	if (isNaN(n) || parseInt(n) != n || n < 0)
		return 'Invalid entry';
	
	else {
		var isPrime = true;
		
		// Checks if n is 2 or 3
		if (n === 2 || n == 3){
			// No action needed, brackets used for readability
		}
		
		// Checks if n is even and sets isPrime to false
		else if (n % 2 === 0)
			isPrime = false;
		
		else
			// Checks if n is divisible by odd numbers less than its square root
			for (var i = 3, j = parseInt(Math.sqrt(n)); i <= j; i = i+2){
				if (n % i === 0){
					isPrime = false;
					break;
				}
			}
		return isPrime;
	}
}

console.log (primeNumberDetector ('13a'));
console.log (primeNumberDetector ('13'));
console.log (primeNumberDetector (13.1));
console.log (primeNumberDetector (-13));
console.log (primeNumberDetector (13));
console.log (primeNumberDetector (25));
console.log (primeNumberDetector (24));

z3r0_c00l · June 9, 2017, 1:10pm

My entry for the intermediate challenge. The primeNumberPrinter primarily just parses the string into single, double, and triple character substrings and pushes any prime numbers found into the result array. I re-used the primeNumberDetector function from the basic challenge and it is here that the “heavy lifting” is done.

The only modification to primeNumberDetector was in the first logic check. I modified the if statement to return false rather than a string.

Shout out to @tomegz for the string I used to test for a triple digit prime.

https://repl.it/Idgt/6

function primeNumberDetector (n){
	
	// Tests to make sure n is an integer greater than 0
	if (isNaN(n) || parseInt(n) != n || n < 0)
		return false;
	
	else {
		var isPrime = true;
		
		// Checks if n is 2 or 3
		if (n == 2 || n == 3){
			// No action needed, brackets used for readability
		}
		
		// Checks if n is even and sets isPrime to false
		else if (n % 2 === 0)
			isPrime = false;
		
		else
			// Checks if n is divisible by odd numbers less than its square root
			for (var i = 3, j = parseInt(Math.sqrt(n)); i <= j; i = i+2){
				if (n % i === 0){
					isPrime = false;
					break;
				}
			}
		return isPrime;
	}
}

function primeNumberPrinter (s){
	var j = 0;
	result = [];
	
	// Iterates through the string looking at single, double, and triple
	// character combinations. Tests each to see if it is a prime number.
	// If it is, it pushes it to the result array.
	for (var i = 0; i < s.length; i++){
		if (primeNumberDetector(s[i]) && s[i] != 1)
			result.push(Number(s[i]));
	
		// Boundry test that i+1 position is within the limit of the string.
		// As substring method is used to parse the string, endpoint is set to i+2
		if (i + 1 < s.length){
			j = i + 2;
			var twoDigit = s.substring(i,j);
			twoDigit = Number(twoDigit);
			if (primeNumberDetector(twoDigit))
				result.push(twoDigit);
			
			// Subsequent boundry test that i+2 position is within the limit of
			// the string. As substring method is used to parse the string, 
			// endpoint is set to i+3
			if (i + 2 < s.length){
				j = i + 3;
				var tripDigit = s.substring(i,j)
				tripDigit = Number(tripDigit);
				if (primeNumberDetector(tripDigit))
					result.push(tripDigit);
			}
		}
	}
	return result;
}

console.log (primeNumberPrinter ('abc2134kd31'));
console.log (primeNumberPrinter ('abc2137kd31'));

micromaster15787 · June 9, 2017, 2:48pm

Thank you Daniel. I’ve edited my contribution now.

Tim

rsm5139 · June 9, 2017, 4:02pm

Ok, here is my basic challenge. I try to eliminate as many as possible before actually looping through numbers and testing them. As far as I can tell, you only need to test up to the square root of the number before it becomes impossible that any number afterward could possibly divide evenly into the number.

https://repl.it/Ie3f/0

factoradic · June 9, 2017, 5:04pm

I am one of the mods involved in the testing and rating process.

The answer is no, you should not make any assumptions towards the length of the digits chains. We can only assure you that in all tests we use strings containing numbers that can be evaluated using built-in types. For example, in Java, you can assume that all digits chain after casting to integer will be less than Integer.MAX_VALUE.

byteslayer90131 · June 9, 2017, 5:55pm

I now know that I should have not imposed restrictions in the number of digits, but I had already started working on this solution for the Intermediate difficulty before doing so. Because I don’t think I’ll have time to complete the “correct” solution before the deadline I thought I would at least post this, so maybe I could get some criticism on this way of solving the problem regarding 3-digit or less numbers.