TransWikia.com

Find the largest contiguous prime in a string

Code Golf Asked by user8777 on February 7, 2021

In fairness, this is based on a StackExchange question – but its a good question.

The challenge is fairly simple:

  1. Take a string of numerals
  2. Find and print the largest contiguous prime number in the string

Scoring:

  • Lowest number of characters wins.
  • Victor will likely be a golfscript entry but we won’t hold that against them, cause we all have fun and learn things, right.
  • Winner we be awarded when I notice that I haven’t actually ticked the green button.

Assumptions:

  • The string is only numbers
    • If the string contains letters, you may have undefined behaviour
  • The string contains at least 1 prime
    • If the string does not contains 1 valid prime number, you may have undefined behaviour
  • Speed is not a constraint
    • Use a shorter prime algorithm over a faster one.
    • If your entry eventually finishes, thats ok, just make sure it will provable happen before the heat death of the universe.
  • The length of the string can be assumed less than 15 characters long

For example:

>> Input:  3571
<< Output: 3571

>> Input:  123
<< Output: 23

>> Input:  1236503
<< Output: 236503

>> Input:  46462
<< Output:  2

>> Input:  4684
<< Output: ValueError: max() arg is an empty sequence

>> Input:  460
<< Output: 0   # Note, zero is not a prime, but the above string has no valid prime

>> Input:  4601
<< Output: 601

>> Input:  "12 monkeys is a pretty good movie, but not as good as se7en"
<< Output: ValueError: Fight Club was also good, I find Brad Pitt to be a consistantly good actor.

Possible implementations:

  1. Find all substrings of the input, check if they are prime. – Legostormtroopr (original)
  2. Find all integers less than input, check if they are in the input then check if it is prime – Ben Reich
  3. Take a list of all primes less than the input, check if it is in the input – daniero

12 Answers

Husk, 6 bytes

→fṗmrQ

Try it online!

Answered by Razetime on February 7, 2021

Japt -h, 6 bytes

ã f_°j

Try it

Answered by Shaggy on February 7, 2021

Jelly, 6 bytes

DẆḌẒƇṀ

Try it online!

Takes input as an integer. If input must be a string, then 7 bytes. Returns 0 for numbers with no primes in them.

How it works

DẆḌẒƇṀ - Main link. Takes n on the left
    Ƈ  - Find...
     Ṁ - ...the largest...
 Ẇ     - ...contiguous...
  ḌẒ   - ...prime...
D      - ...in a string

or, alternatively,

DẆḌẒƇṀ - Main link. Takes n on the left
D      - Convert n to digits
 Ẇ     - Get all contiguous sublists
  Ḍ    - Convert each back from digits
    Ƈ  - Filter keep:
   Ẓ   -   Primes
     Ṁ - Yield the maximum

Answered by caird coinheringaahing on February 7, 2021

Perl 6 (40 characters, 41 bytes)

$_=get;say max grep &is-prime,+«m:ex/.+/

First get input into $_, this makes the regex match call shorter. :ex gives exhaustive matching for regex, it will give all possibilities. The hyper op (or +<< works too) will make numbers out of the Match objects, those are passed to grep with &is-prime sub as selector. Finally take the maximum of the remaining list and output it.

Answered by Ayiko on February 7, 2021

Perl 6 (50 characters, 51 bytes)

say max +«get.match(/(.+)<?{(+$0).is-prime}>/,:ex)

maps strings to numbers, max gets the biggest number, get receives a line. /(.+)<?{(+$0).is-prime}>/ is a regular expression that gets all primes <?{}> is a code assertion. is-prime is Int class method which checks if number is a prime. I need to cast value to number by using +, because it's Str by default. :ex means that it tries to find ALL matches (including those where overlap others). Because of Rakudo Perl bug, it's currently impossible to use m// here.

This works for any number, and if you remove max (or replace it with sort) you will get list of all primes in the number, for extra bonus (not that this gives points, or anything). For example (with sort in this case):

1234567890
2 3 5 7 23 67 89 4567 23456789

Answered by Konrad Borowski on February 7, 2021

J (24 22)

Reading from the keyboard is actually shorter than defining a function.

>./(*1&p:);"..1!:1[1

Test:

   >./(*1&p:);"..1!:1[1
3571
3571
   >./(*1&p:);"..1!:1[1
46462
2
   >./(*1&p:);"..1!:1[1
1236503
236503
   >./(*1&p:);"..1!:1[1
4684
0
   >./(*1&p:);"..1!:1[1
4680
0
   >./(*1&p:);"..1!:1[1
twelve monkeys is a pretty good movie
__

Explanation:

  • 1!:1[1: read a line of text from the keyboard
  • "..: the evaluation (".) of each suffix (.) of each prefix () of the string.
  • ;: flatten the matrix
  • *1&p:: multiply each value by whether it is a prime or not (so all nonprimes will be zero)
  • >./: get the largest value in the list

Answered by marinus on February 7, 2021

Scala (83 chars)

I wasn't sure how to provide inputs to the program so I considered n is the input. Here's the actual solution (based on which the solution length is evaluated). Below that is an executable form of the solution (which isn't golfed yet) for execution along with the output (for the samples give OP has).

Solution:

n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max

Executable solution:

object A {
  def main(x:Array[String])=List("3571","123","23","1236503","46462","4684","460","4601","12 monkeys..").foreach(e=>println(e+" => "+q(e)))

  private def p(n: String)=n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max
  private def q(n: String)=try p(n)catch{case e=>e.toString}
}

Sample output:

3571 => 3571
123 => 23
23 => 23
1236503 => 236503
46462 => 2
4684 => java.lang.UnsupportedOperationException: empty.max
460 => java.lang.UnsupportedOperationException: empty.max
4601 => 601
12 monkeys.. => java.lang.NumberFormatException: For input string: "12 "

Explanation:

Steps are pretty straight forward.

input -> Find all substrings -> filter non primes -> find longest value

  • main(Array[String]): Method provides sample input and executes method q(String) for each input
  • q(String): Wraps actual program logic from p(String) so any exceptions are appropriately reported. Helps in formatting the output better because invalid inputs are going to get NumberFormatExceptions where as the lack of a prime will throw an UnsupportedOperationException
  • p(String): Actual logic of the program. Let's split the explanation for this into parts
    • n.inits: Creates an Iterator to iterate over the String input (n)
    • flatMap(f): Applies an operation on the Iterator and pushes the result into a List
      • _.tails.toList.init.map(BigInt(_)): Splits the String and removes empty Strings from the resultant List. Finally converts the String to a BigInt which is an equivalent of java.math.BigInteger. For golfing reasons, BigInt is selected (shorter name).
    • filter(f): if f returns false, the value is removed from the resultant List
      • _ isProbablePrime 1: This line could have been written as _.isProbablePrime(1) but the representation used saves 1 byte. This line actually checks if the value is a prime (probabilistically; since certainty is set to 1, execution time goes up but the system makes certain (more or less) that the number is a prime.
    • max: Finds the maximum value (not String based length. Actual max value)

Answered by javatarz on February 7, 2021

Haskell, 94

main=getLine>>=print.maximum.filter(x->and$map((0/=).mod x)[2..x-1]).map read.init.scanr(:)[]

Answered by Vektorweg on February 7, 2021

Ruby 61

Take all primes up to N and see if they are in the string

require'prime'
p Prime.each(gets.to_i).select{|i|~/#{i}/}.max

I think this only works on Ruby 1.9 and newer, but I'm not sure.

Answered by daniero on February 7, 2021

Mathematica 67 47

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&

Explanation

The code is a pure function. It has no name. In it, # represents the full input string.

StringCases takes the input, #, and checks for substrings, a, of one character or more (that's why __ was used instead of _) that are primes; PrimeQ must return True for the substring.

All the favorable cases, i.e. the substrings that are primes, are by default returned in a list. 〚1〛, or [[1]] takes the first part, that is, the first element of that list of primes. element[[1]] is shorthand for Part[element, 1]. If there is more than one prime, the first one will be the longest prime (StringCases checks the longest substrings first).

Examples

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&["1236503"]

"236503"

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&/@ 
{"1236503", "123", "46462", "4684", "460", "4601", 
"12 monkeys is a pretty good movie, but not as good as se7en"}

{"236503", "23", "2", {}[[1]], {}[[1]], "601", "2"}

Answered by DavidC on February 7, 2021

GolfScript 40 37

.{``?)}+~),,{.,(;{%!}+,,1=},);

This looks at all numbers less than or equal to the the input, filters down to the ones that are substrings of the input, and then filters further down to the primes. Then, it takes the largest such element (which is obviously guaranteed to have the most digits).

Let's break it down into two main sections:

.{``?)}+~,,

This part of the code filters down to all integers string contained in the input. It uses grave accent to turn numbers into strings, and then ? to determine the index of the substring. Since ? returns -1 in the case of no containment, increment using ) so that the output is 0 for non-substrings, which will behave nicely with the , filtering.

{.,(;{%!}+,,1=},

This part of the code filters down to the primes by counting the number of factors less than the given number (an integer is a factor only if number factor %! is 1. A prime number will have exactly 1 factor strictly less than itself, so do 1=.

Since the numbers are in order, take the last one and clear the stack using );

This obviously isn't as efficient as possible (since it somewhat unnecessarily iterates over all integers less than the input), but it still terminates with big input like 1236503 relatively quickly on my computer (1 minute).

Answered by Ben Reich on February 7, 2021

Python 2.7 - 84

Here is a reference implementation to beat, I used it for the example output in the question, so its gauranteed to work * Not an actual guarantee

Shameless improvement based on Ben Reich's much better solution than my original one. With major assistance from Volatility

N=input()
print max(x for x in range(N+1)if(`x`in`N`)&all(x%i for i in range(2,x)))

Prior incantations of the second line include:

print max(x for x in range(N+1)if`x`in`N`and 0 not in(x%i for i in range(2,x)))
print max(x for x in range(N+1)if`x`in`N`and sum(x%i<1 for i in range(2,x))<1)

The original version - 143

N=`input()`
p=lambda n:[n%i for i in range(2,n)if n%i==0]
print max(int(N[j:i])for i in range(len(N)+1)for j in range(i)if not p(int(N[j:i])))

Answered by user8777 on February 7, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP