# 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 small. Numbers of this type are useful for the fast Fourier transform algorithm, cryptanalysis, and other applications.

For instance, over the range `5, 6, 7, 8, 9, 10`, 8 is the smoothest number, because 8's greatest prime factor is 2, whereas all of the other numbers have a prime factor of 3 or greater.

Input: The input will be two positive integers, which define a range. The minimum allowable integer in the range is 2. You may choose whether the range is inclusive, exclusive, semi-exclusive, etc, as long as an arbitrary range can be specified within the bounds of your language. You may take the numbers via function input, stdin, command line argument, or any equivalent method for your language. No encoding extra information in the input.

Output: Return, print or equivalent one or more integers in the input range which are maximally smooth (minimal greatest factor). Returning multiple results is optional, but if you choose to do so the results must be clearly delimited. Native output format is fine for multiple results.

Scoring: Code golf. Count by characters if written in ASCII, or 8*bytes/7 if not in ASCII.

Test cases:

Note: These are Python-style ranges, including the low end but not the high end. Change as appropriate to your program. Only one result is necessary.

``````smooth_range(5,11)
8
smooth_range(9,16)
9, 12
smooth_range(9,17)
16
smooth_range(157, 249)
162, 192, 216, 243
smooth_range(2001, 2014)
2002
``````
-
Are ranges specified as (start,length) instead of (start,end) acceptable? – CodesInChaos Aug 21 '14 at 16:26
@CodesInChaos Sure. It's covered under the "or whatever" clause. – isaacg Aug 21 '14 at 17:09
I don't see the point in penalizing non-ASCII answers. It would be simpler to just count bytes in all cases. – nyuszika7h Aug 21 '14 at 17:59
@nyuszika7h Ascii is significantly smaller than a byte - it only uses 7 bits. Therefore, I denote one character by 7 bits, and scale other languages accordingly. However, if the language is non-ASCII but can pack all of its characters into 7 bits, I will not apply the surcharge. See J/K vs. APL. tl;dr Bytes is simpler, but gives APL et. al. a subtle but unfair advantage. – isaacg Aug 21 '14 at 18:31
@isaacg you're encouraging the creation of pseudo-languages using smaller character sets. if we score 7-bit character sets different from 8-bit character sets, someone can pack most modern languages into 6 bits (64 characters gets us A-Z, 0-9, a handful of whitespace, 20 punctuation, and a few to spare). – Sparr Mar 8 '15 at 7:14

# CJam - 13

``````q~,>{mfW=}\$0=
``````

Example input: `2001 2014`
Example output: `2002`

Explanation:

`q~` reads and evaluates the input, pushing the 2 numbers on the stack (say min and max)
`,` makes an array [0 1 ... max-1]
`>` slices the array starting at min, resulting in [min ... max-1]
`{…}\$` sorts the array using the block to calculate the sorting key
`mf` gets an array with all the prime factors of a number, in order
`W=` gets the last element of the array (W=-1), thus obtaining the largest prime factor to be used as a sorting key
`0=` gets the first element of the (sorted) array

-
Well, I guess that's that. – Eric Tressler Aug 19 '14 at 0:23
I need to add a factorize function to pyth. – isaacg Aug 19 '14 at 0:45
This language is wizardry. – Brobin Aug 19 '14 at 3:52
This is as close to just pulling some HQ9+ s**t as it can be without becoming a loophole. Awesome! – Ingo Bürk Aug 19 '14 at 19:45
ヽ༼ຈل͜ຈ༽ﾉ `mfW` someone solved it in 13 chars. – teh internets is made of catz Aug 19 '14 at 22:48

## Regex (.NET PCRE flavour), 183 129 bytes

Don't try this at home!

This is not really a contender for the win. But Eric Tressler suggested solving this problem with nothing but a regex, and I couldn't resist giving it a go. This might be is possible in PCRE as well (and even shorter, see below), but I chose .NET because my solution needs arbitrary-length lookbehinds. Here we go:

``````(?<=^(1+),.*)(?=\1)(?=((11+)(?=.*(?=\3\$)(?!(11+?)\4+\$))(?=\3+\$)|(?!(11+)\5+\$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((11+)(?=.*(?=\7\$)(?!(11+?)\8+\$))(?=\7+\$)|(?!(11+)\9+\$)1+)).*(?=\2\$)(?=\6)))1+
``````

The input is encoded as an inclusive comma-separated range, where both numbers are given in unary notation using `1`s. The match will be the trailing `S` 1s where `S` is the smoothest number in the range. Ties are broken in favour of the smallest number.

So the second example from the question would be the following string (match underlined)

``````111111111,1111111111111111
=========
``````

It is based on the (by now rather well-known) prime-checking regex, variations of which are embedded in there a whopping 6 times.

Here is a version using free-spacing and comments for those who want to know what's going on.

``````# Note that the beginning of the match we're looking for is somewhere
# in the second part of the input.
(?<=^(1+),.*)          # Pick up the minimum range MIN in group 1
(?=\1)                 # Make sure there are at least MIN 1s ahead

# Now there will be N 1s ahead of the cursor
# where MIN <= N <= MAX.

(?=(                   # Find the largest prime factor of this number
# store it in group 2.
(11+)                # Capture a potential prime factor P in group 3
(?=                  # Check that it's prime
.*(?=\3\$)          # Move to a position where there are exactly
(?!(11+?)\4+\$)     # Check that the remaining 1s are not composite
)
(?=\3+\$)             # Now check that P is a divisor of N.
|                      # This does not work for prime N, so we need a
# separate check
(?!(11+)\5+\$)        # Make sure that N is prime.
1+                   # Match N
))

(?!                    # Now we need to make sure that here is not
# another (smaller) number M with a smaller
# largest prime factor

.+                   # Backtrack through all remaining positions
(?=\1)               # Make sure there are still MIN 1s ahead

(?:
(?!\2)             # If M is itself less than P we fail
# unconditionally.
|                    # Else we compare the largest prime factors.
(?=(               # This is the same as above, but it puts the
# prime factor Q in group 6.
(11+)
(?=
.*(?=\7\$)
(?!(11+?)\8+\$)
)
(?=\7+\$)
|
(?!(11+)\9+\$)
1+
))
.*(?=\2\$)          # Move to a position where there are exactly
(?=\6)             # Try to still match Q (which means that Q is
# less than P)
)
)
1+                     # Grab all digits for the match
``````

You can test it online over here. Don't try too large inputs though, I make no guarantees about the performance of this monster.

Edit:

I ended up porting this to PCRE (which only requires two steps), and shortening the regex by almost a third. Here is the new version:

``````^(1+),.*?\K(?=\1)(?=((11+)(?=.*(?=\3\$)(?!(11+?)\4+\$))(?=\3+\$)|(?!(11+)\5+\$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((?2))).*(?=\2\$)(?=\6)))1+
``````

This is essentially the same, with two changes:

• PCRE does not support arbitrary-length lookbehind (which I used to get the `MIN` into group `1`). However, `PCRE` does support `\K` which resets the beginning of the match to the current cursor position. Hence `(?<=^(1+),.*)` becomes `^(1+),.*?\K`, which already saves two bytes.
• The real savings come from PCRE's recursion feature. I'm not actually using recursion, but you can use `(?n)` to match group `n` again, similar to a subroutine call. Since the original regex contained the code for finding a number's largest prime factor twice, I was able to replace the whole bulk of the second one with a simple `(?2)`.
-
Holy mother of god – Newb Aug 21 '14 at 0:51
You write “This does not work for prime N, so we need a separate check”. However, could you not make it work for prime N simply by changing `(=\3+\$)` to `(=\3*\$)` (and also `(=\7+\$)` to `(=\7*\$)`) and then save yourself the extra primality check? This would save 32 characters. – Timwi Sep 4 '15 at 19:36
@Timwi I need to check that the largest prime factor (group `3` or `7`) is actually prime. This requires that there is another copy of the factor after first capturing it, which wouldn't be the case for primes. While I work around that in .NET by putting a lookbehind somewhere in there such that I could move back a bit for the check, this wouldn't be possible in the shorter PCRE version due to the lack of variable-length lookbehinds. It probably is possible to shorten that bit, but I don't think just changing `+` to `*` works. – Martin Ender Sep 4 '15 at 21:15

# Python 2, 95

``````i=input()
for a in range(*i):
s=a;p=2
while~-a:b=a%p<1;p+=1-b;a/=p**b
if p<i:i=p;j=s
print j
``````

Finds the smoothness of the the numbers by trial division until the number is 1. `i` stores the smallest smoothness so far, `j` stores the number that gave that smoothness.

Thanks to @xnor for the golfs.

-
That `if/else` has got to be shortenable. My first thought is `b=a%p<1;p+=1-b;a/=p**b`. Or an exec that runs one of the two in an interleaved string. Also, maybe `while~-a` works. – xnor Aug 19 '14 at 1:24
isaacg — I love this answer! What a brilliant way you found to search for the largest prime factor! I have updated my answer to borrow your method, with credit to you on the method. – Todd Lehman Aug 19 '14 at 4:03
Great solution! Using `s,p=a,2`, `i,j=p,s`, @xnor's ideas, removing redundant indentation and putting the while block into one line yields 95 characters. Not sure how you came up with 98... – Falko Aug 19 '14 at 5:30
this code is full of emoticons, :) – Rosenthal Aug 19 '14 at 6:32
@Falko those two changes save no characters. 7->7. – isaacg Aug 19 '14 at 7:55

## Mathematica, 6145 39 characters

``````Range@##~MinimalBy~Last@*FactorInteger&
``````

Very straightforward implementation of the spec as an unnamed function.

• Get the range (inclusive).
• Factor all integers.
• Find the minimum, sorted by largest prime factor.
-

## J, 22 20 19 chars

``````({.@/:{:@q:)@(}.i.)
``````

E.g.

``````   2001 ({.@/: {:@q:)@(}. i.) 2014
2002
``````

(Functions taking two arguments are infix in J.)

-
I also had a crack at it, didn't get it as short as this answer. Still: `(#~ (= <./)@:(i:"1&1)@:*@:(_&q:))@:([ + i.@-~)` – ɐɔıʇǝɥʇuʎs Aug 20 '14 at 14:33
Here `{:` is the same as `>./` and saves 1 byte. – randomra Mar 8 '15 at 1:34
@randomra You're right—good call! – FireFly Mar 8 '15 at 17:14

``````x%y|x<2=y|mod x y<1=div x y%y|0<1=x%(y+1)
a#b=snd\$minimum\$map(\x->(x%2,x))[a..b]
``````

usage via GHCi (a Haskell shell):

``````>5 # 9
8
>9 # 15
9
``````

EDIT: now a much simpler algorithm.

this solution includes both numbers in the range (so `8 # 9` and `7 # 8` are both 8)

explanation:

the (%) function takes two parameters, x and y. when y is 2, the function returns the smoothness of x.

the algorithm from here is simple - get the combined list of all smoothnesses of numbers in the input with each smoothness storing a reference to it's original number, sort then to get the smallest, and return it's referenced number.

here is an ungolfed javascript version with the same algorithm:

``````function smoothness(n,p)
{
p = p || 2
if (x == 1)
return p
if (x % p == 0)
return smoothness(x/p, p)
else
return smoothness(x,p+1);
}
function smoothnessRange(a, b)
{
var minSmoothness = smoothness(a);
var min=a;
for(var i=a+1;i <= b;i++)
if(minSmoothness > smoothness(i))
{
minSmoothness = smoothness(i)
min = i
}
return min;
}
``````
-
Would it be possible to alias minimum to something shorter? That looks like it would save some characters. – isaacg Aug 19 '14 at 19:43
I tried it, but because of the monomorphism restriction it actually costs one character – proud haskeller Aug 19 '14 at 19:44
You can't just do m=minimum? Haskell is still a mystery. – isaacg Aug 19 '14 at 19:45
No, because of the monomorphism restriction. It is something to do with type classes – proud haskeller Aug 19 '14 at 19:46
I was going to post a Haskell solution, until I saw yours which beats even my incomplete version... +1 – nyuszika7h Aug 21 '14 at 18:31

# Lua - 166 chars

I don'tdidn't have (yet!) enough reputation to comment on AndoDaan's solution, but here are some improvements on his code

``````a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d<1 do f[#f+1]=d n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)
``````

Changes :

• The `n%d==0` by `n%d<1` which is equivalent in this case
• Removed a space
• Replaced `table.insert(f,d)` by `f[#f+1]=d` (`#f` is the number of elements of f)
-
Ah, glad I glanced here. Ah, the first two i should have checked and caught, but your third improvement is new to me (I mean just different than what I'm used to). That's going to help me a lot here and over at golf.shinh.com. Thanks! – AndoDaan Aug 19 '14 at 21:50

# Bash+coreutils, 56 bytes

``````seq \$@|factor|sed 's/:.* / /'|sort -nk2|sed '1s/ .*//;q'
``````

Input is from from exactly two command-line arguments (Thanks @nyuszika7h !!!). Output is a singular result printed to STDOUT.

• `seq` provides the range of numbers, one per line, from the command-line arguments.
• `factor` reads those numbers and outputs each number followed by a colon and the sorted list of prime factors of that number. So the largest prime factor is at the end of each line.
• The first `sed` removes the colon and all but the last/largest prime factor, so leaves a list of each number (column 1) and its largest prime factor (column 2).
• `sort` numerically in increasing order by the column 2.
• The final `sed` matches line 1 (number whose largest prime factor is the smallest in the list), removes everything including and after the first space, then quits. `sed` automatically prints the result of this substitution before quitting.

### Output:

``````\$ ./smooth.sh 9 15
12
\$ ./smooth.sh 9 16
16
\$ ./smooth.sh 157 249
162
\$ ./smooth.sh 2001 2014
2002
\$
``````

Note ranges in this context are inclusive of both endpoints.

-
`seq \$@` is 3 bytes shorter, if you can assume that there are only two arguments. – nyuszika7h Aug 21 '14 at 18:36
@nyuszika7h Nice idea - thanks! – Digital Trauma Aug 21 '14 at 18:48

## C,  149   95

I cannot claim credit for this solution. This updated answer borrows the beautiful method used by isaacg in his Python solution. I wanted to see if it was possible to write it in C as a nested `for`/`while` loop with no curly braces, and it is!

``````R(a,b,n,q,p,m){for(;a<b;m=p<q?a:m,q=p<q?p:q,n=++a,p=2)while(n>1)if(n%p)p++;else n/=p;return m;}
``````

Explanation:

• Function `R(a,b,n,q,p,m)` scans the range `a` to `b-1` and returns the first smoothest number found. Invocation requires adherence to the following form: `R(a,b,a,b,2,0)` so that variables inside the function are effectively initialized as follows: `n=a;q=b;p=2;m=0;`.

``````P(n,f,p){for(;++f<n;)p=p&&n%f;return p;}
G(n,f){for(;--f>1;)if(n%f==0&&P(f,1,1))return f;}
R(a,b,p,n){for(;++p;)for(n=a;n<b;n++)if(G(n,n)==p)return n;}
``````

Explanation:

• Function `P(n,f,p)` tests value `n` for primality and returns true (nonzero) if `n` is prime or false (zero) if `n` is non-prime. `f` and `p` must both be passed as 1.
• Function `G(n,f)` returns the greatest prime factor of `n`. `f` must be passed as `n`.
• Function `R(a,b,p,n)` scans the range `a` to `b-1` and returns the first smoothest number found. `p` must be passed as 1. `n` can be any value.

Test driver:

``````test(a,b){printf("smooth_range(%d, %d)\n%d\n",a,b,S(a,b,1,0));}
main(){test(5,11);test(9,16);test(9,17);test(157,249);test(2001,2014);}
``````

Output:

``````smooth_range(5, 11)
8
smooth_range(9, 16)
9
smooth_range(9, 17)
16
smooth_range(157, 249)
162
smooth_range(2001, 2014)
2002
``````
-
I would argue this falls foul of "No encoding extra information in the input" clause. – Alchymist Aug 21 '14 at 23:02
@Alchymist — You may be right...but I don't think there's any actual extra information in the pseudo-arguments. At least not any information that is any kind of clue as to the answer. – Todd Lehman Aug 21 '14 at 23:29

## Q, 91 characters K, 78 characters

``````{(x+{where x=min x}{(-2#{x div 2+(where 0=x mod 2_til x)@0}\[{x>0};x])@0}'[(x)_til y+1])@0}
``````

k would probably shave a dozen characters

edit: indeed, treating the upper bound as non inclusive this time

``````{*:x+{&:x=min x}{*:-2#{6h\$x%2+*:&:x={y*6h\$x%y}[x]'[2_!x]}\[{x>0};x]}'[(x)_!y]}
``````
-

# Note: This answer is not allowable.

I added another new feature, calling unary range on a 2 element tuple, which shortens the solution by two characters, to this:

# Pyth, 7

``````hoePNUQ
``````

Input is now taken comma separated. The rest is the same.

This answer uses a feature of Pyth that was added after this question was asked, specifically after seeing @aditsu's wonderful CJam solution. That being said, I wanted to demonstrate what adding that feature has made possible. The feature is `P`, which is an arity-1 function which on integer input returns a list of all prime factors of the input, sorted smallest to largest.

# Pyth, 9

``````hoePNrQvw
``````

Uses Python-style ranges, newline separated on STDIN. Outputs smallest solution to STDOUT.

Explanation:

``````      Q = eval(input())                         Implicit, because Q is present.
o         order_by(                            Sort, using lambda expression as key.
lambda N:                   Implicit in o
e                          end(               Last element of
PN                            pfact(N)),     List containing all prime factors of N.
r                 range(                      Python-style range, lower inc, upper exc.
Q                      Q,                    A variable, initialized as shown above.
vw                     eval(input()))))      The second entry of the range, same way.
``````

Tests:

``````\$ newline='
'

\$ echo "9\${newline}16" | ./pyth.py -c 'hoePNrQvw'
9

\$ echo "9\${newline}17" | ./pyth.py -c 'hoePNrQvw'
16

\$ echo "157\${newline}249" | ./pyth.py -c 'hoePNrQvw'
162

\$ echo "2001\${newline}2014" | ./pyth.py -c 'hoePNrQvw'
2002
``````
-
@MartinBüttner Yep, as suggested by his comment on the CJam solution – Adriweb Aug 21 '14 at 12:22
@MartinBüttner Yeah, P, is the new feature. I'll put that in the answer. – isaacg Aug 21 '14 at 12:32
Allowable or not, not only I like it, but I also think that those short "macros" are readable if you pay attention - they convert to straightforward Python, after all. Something has to be said for a golf language that is good for golf but not necessarily obfuscating. – Kuba Ober Aug 21 '14 at 14:52
@KubaOber Thanks, Kuba. That's always been my intention in writing Pyth, to make it as golfed and as readable as possible. I'm glad it's working. – isaacg Aug 21 '14 at 20:47

# Python 2, 67

``````f=lambda R,F=1,i=2:[n for n in range(*R)if F**n%n<1]or f(R,F*i,i+1)
``````

Thinking about another golf gave me an idea for a new algorithm to check smoothness, hence the late answer.

The prime factorization of the factorial `i!` includes exactly the primes at most `i`. So, if `n` is a product of distinct primes, its smoothness (largest prime factor) is the smallest `i` for which `n` is a divisor of `i!`. To account for repeated prime factors in `n`, we can instead use a sufficiently high power of `i!`. In particular, `(i!)**n` suffices.

The code tries increasing factorials `F=i!`, updated recursively. We filter for the divisors of `F` in the input range, and output them if there are any, and otherwise move on to `(i+1)!`.

Test case:

``````>> f([157, 249])
[162, 192, 216, 243]
``````
-

# Lua - 176 characters

``````a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d==0 do table.insert(f, d)n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)
``````

I really should stop golfing in Lua. There's no point.

-
IMHO, code golfing is like boxing: there are weight-classes. A given language may not win outright, but it is fun and illuminating to golf within that class/language. – Michael Easter Aug 19 '14 at 1:26

``````import Data.List
import Data.Ord
x!y=(minimumBy(comparing(%2)))[x..y]
x%y|x<y=y|x`mod`y==0=(x`div`y)%y|otherwise=x%(y+1)
``````

Example usage:

``````> 5 ! 10
8
> 9 ! 15
9
> 9 ! 16
16
> 157 ! 248
162
> 2001 ! 2013
2002
``````
-

## Clojure - 173 170 chars

I'm a Clojure newbie. Golfed:

``````(defn g[x,d](if(and(= 0(mod x d))(.isProbablePrime(biginteger d) 1))d 0))(defn f[i](apply max-key(partial g i)(range 2(inc i))))(defn s[a,b](first(sort-by f(range a b))))
``````

Sample runs:

Ranges include low-end, exclude high-end: [a,b) Only prints one of the smoothest numbers, if multiple occur.

``````(println (s 5 11))
(println (s 9 16))
(println (s 9 17))
(println (s 157, 249))
(println (s 2001, 2014))
``````

yields:

``````bash\$ java -jar clojure-1.6.0.jar range.clj
8
9
16
192
2002
``````

Ungolfed:

``````(defn g [x,d] (if (and (= 0(mod x d)) (.isProbablePrime (biginteger d) 1)) d 0))
(defn f [i] (apply max-key (partial g i) (range 2 (inc i))))
(defn s [a,b] (first (sort-by f (range a b))))
``````
-
A range that includes the low end and excludes the high end is usually written [a,b). – murgatroid99 Aug 19 '14 at 17:12
yep, thanks for the note – Michael Easter Aug 19 '14 at 17:23

# Ruby, 65 62

``````require'prime'
s=->a,b{(a..b).min_by{|x|x.prime_division[-1]}}
``````

With apologies to http://codegolf.stackexchange.com/a/36484/6828, this is the golfed (and slightly simplified) version of that. Uses an inclusive range since it's a character shorter.

``````1.9.3-p327 :004 > s[157,249]
=> 192
1.9.3-p327 :005 > s[5,11]
=> 8
1.9.3-p327 :006 > s[9,15]
=> 12
1.9.3-p327 :007 > s[9,16]
=> 16
``````

And thanks to YenTheFirst for saving three characters.

-
You can actually get away without the [0], since array comparison will prioritize the first element anyway. This will give different, but still correct, results. – YenTheFirst Aug 20 '14 at 22:39

## C# LINQ: 317303289 262

``````using System.Linq;class P{static void Main(string[]a){System.Console.Write(Enumerable.Range(int.Parse(a[0]),int.Parse(a[1])).Select(i=>new{i,F=F(i)}).Aggregate((i,j)=>i.F<j.F?i:j).i);}static int F(int a){int b=1;for(;a>1;)if(a%++b<1)while(a%b<1)a/=b;return b;}}
``````

Ungolfed:

``````using System.Linq;

class P
{
static void Main(string[]a)
{
System.Console.Write(
Enumerable.Range(int.Parse(a[0]), int.Parse(a[1])) //create an enumerable of numbers containing our range (start, length)
.Select(i => new { i, F = F(i) }) //make a sort of key value pair, with the key (i) being the number in question and the value (F) being the lowest prime factor
.Aggregate((i, j) => i.F < j.F ? i : j).i); //somehow sort the array, I'm still not entirely sure how this works
}
static int F(int a)
{
int b=1;
for(;a>1;)
if(a%++b<1)
while(a%b<1)
a/=b;
return b;
}
}
``````

It takes in the start and the length from the command line and will return the largest smooth number.

Thanks to VisualMelon for tweaking it and shaving 12 bytes off! I also got rid of the braces in the if saving 2 bytes, and CodeInChaos pointed out some obvious stuff I missed (thanks again).

-
Couple of general purpose small things, you can save 4 bytes in `F` by defining `int b` next to m. In a couple of places you perform the comparison `a%b==0`, and `a` and `b` are always positive you can cut a byte for each by checking if it's less than 1 `a%b<1`. You can also save a byte by incrementing `b` in the if's condition `a%++b<0` rather than in the for by initializing it to 1. I also think in this case it's cheaper to just fully qualify `System.Console.WriteLine` and avoid the `namespace` clause. – VisualMelon Aug 20 '14 at 18:57
@VisualMelon Thanks, updated with your ideas :) – Logan Dam Aug 21 '14 at 6:49
The `m=...:m;` thingy falls outside the while loop. Therefore, you can drop the `m=0,` and replace `return m;` with `return m=b>m?b:m;`. Then, you can drop the `m=...:m;` entirely. – tomsmeding Aug 21 '14 at 11:54
It may sound weird, but this is - to me- less redable than CJam and J. I guess C# was designed to be verbose, and attempts at making it less so make it unreadable? Hmm.... – Kuba Ober Aug 21 '14 at 14:49
No I agree, LINQ looks like a demon when you just see it here and there and never actually play with it yourself. Once you grasp it though, it's really cool :) With that said, I still don't fully understand how `Aggregate` works, I just tried it after seeing it in another answer to get to my new object instead of just one field within it, and it just happened to work perfectly :) – Logan Dam Aug 21 '14 at 15:08

# J - 16 char

Using the (start, length) style of range, as allowed by the comments.

``````(0{+/:{:@q:@+)i.
``````

To be used as a dyadic verb: left argument is start, right is length.

``````   5 (+)i. 6              NB. range
5 6 7 8 9 10
5 (q:@+)i. 6           NB. prime factorizations
5 0 0
2 3 0
7 0 0
2 2 2
3 3 0
2 5 0
5 ({:@q:@+)i. 6        NB. largest prime factors
5 3 7 2 3 5
5 (+/:{:@q:@+)i. 6     NB. sort range by smallest factors
8 6 9 5 10 7
5 (0{+/:{:@q:@+)i. 6   NB. take first entry
8
f=:(0{+/:{:@q:@+)i.    NB. can also be named
2001 f 13
2002
``````

A (start, end) solution is +2 chars, and excludes the end; including the end is +2 more. But on the bright side, it looks rather nice since we match up all the {braces}.

``````(0{}./:{:@q:@}.)i.    NB. excluding
(0{}./:{:@q:@}.)1+i.  NB. including
``````
-

## Seriously, 8*14/7 = 16 (non-competitive)

``````,x;`yM`M;m@í@E
``````

Seriously was created after this challenge, but I wanted to post this answer because it exemplifies the type of challenges Seriously is good at.

Try it online!

Explanation:

``````,x;`yM`M;m@í@E
,x;             make two copies of range(a,b) (a,b = input())
`  `M;       make two copies of the result of the map:
yM            push maximum prime factor
m@í    push index of minimum element from prime factors
@E  push element from range with given index
``````
-

# Cobra - 150

``````def f(r as vari int)
x,y=r
c,o=y,0
for n in x:y,for m in n:0:-1
p=1
for l in 2:m,if m%l<1,p=0
if n%m<=0<p
if m<c,c,o=m,n
break
print o
``````

Not even sure why I bothered, cobra just can't compete here.

-
Cobra looks identical to python... What are the differences? – Beta Decay Aug 20 '14 at 9:29
@BetaDecay Cobra is what happens when you give C# the syntax of Python. The Cobra Website – Ourous Aug 20 '14 at 11:35
Wow, that's nice! – Beta Decay Aug 20 '14 at 12:13

# Ruby - 113 chars

Using the stdlib. Returns one result. Tested on ruby 2.1.2.

``````require 'prime'
def smooth_range(a,b)
(a...b).sort_by{|e|e.prime_division.flat_map{|f,p|[f]*p}.uniq.max}[0]
end
``````
-
Welcome to Programing Puzzles and Code Golf Stack Exchange. Thanks for posting your result. Since this is a code-golf question, please include your character count in your answer. You can use a tool such as this one: javascriptkit.com/script/script2/charcount.shtml – isaacg Aug 20 '14 at 0:34

## R, 83

``````library(gmp)
n=a:b
n[which.min(lapply(lapply(lapply(n,factorize),max),as.numeric))]
``````

where the bottom of the input range is assigned to `a` and the top (inclusive) is assigned to `b`.

`gmp` is a package that is available on CRAN. It felt dirty until I saw that absurd `mf` function in CJam. Install by typing `install.packages("gmp")` in the console.

-
If you're using `lapply` 3 times you might want to alias it (i. e. `l=lapply` and then use `l(...`). Similarly since `factorize` is the only function you use from package `gmp` you can use `gmp::factorize` instead of loading the library and then using `factorize`. Your code thus would become `l=lapply;n=a:b;n[which.min(l(l(l(n,gmp::factorize),max),as.numeric))]` which is 69 bytes. – plannapus May 10 at 7:07

## PowerShell - 85

``````(\$args[0]..\$args[1]|sort{\$d=2
while(\$_-gt1){while(!(\$_%\$d)){\$m=\$d;\$_/=\$d}\$d++}\$m})[0]
``````

This will sort a range of numbers (inclusive) based on each number's max prime factor. It returns the lowest sorted element.

``````> smooth 5 10
8
> smooth 9 15
12
> smooth 9 16
16
> smooth 157 248
243
> smooth 2001 2013
2002
``````
-

## Perl (5.10+), 83

``````for(<>..<>){\$n=\$_;\$p=2;\$_%\$p&&\$p++or\$_/=\$p while\$_>1;\$m=\$p,\$r=\$n if\$p<\$m||!\$m}
say\$r
``````

(linebreak can be removed). Takes two endpoints of an inclusive range on two lines of stdin (because `<>` is cheaper than accessing `ARGV`) and outputs the smoothest to stdout. If there's a tie for smoothest, prints the smallest. Could print the biggest at the cost of one character.

The algorithm is basically isaacg's way of finding the greatest prime factor, although we came up with it independently. That part golfs down beautifully to a single statement in perl, the rest has more overhead than I'd like though.

Should be run under `perl -E` or with a `use 5.012` preamble. If you can't do that, replace `say\$r` with `print\$r,\$/`.

-

# Python 2 (84)

``````f=lambda n,p=2:n>1and f(n/p**(n%p<1),p+(n%p>0))or p
print min(range(*input()),key=f)
``````

@isaacg's solution, but with a `min` by function key in place of explicit min-finding, and a recursive function playing the role of the iteration.

Run in Stackless Python to avoid recursion limits.

It looks wasteful to use the paranthesized condition `(n%p<1)`, then repeat its negation also in parantheses `(n%p>0)`, but that was the best I got. I tried things a bunch of things, but they turned out worse.

``````f(n/p**(n%p<1),p+(n%p>0))     # Current for comparison
f(*[n/p,n,p,p+1][n%p>0::2])
n%p and f(n,p+1)or f(n/p,p)
f(*n%p and[n,p+1]or[n/p,p])
``````

I welcome any improvements you can think of.

-

## Java 8 - 422 454 chars

I'm learning Java 8, and wanted to give this a shot relative to Java (or even Java 8 streams).

Compared to other languages, this is brutal but an interesting exercise.

Golfed:

``````import java.util.stream.*;import java.math.*;
class F{int v;int i;public int getV() { return v; }
F(int i){this.i = i;v=IntStream.range(2,i+1).map(j->((i%j==0)&&new BigInteger(""+j).isProbablePrime(1))?j:0).max().getAsInt();}}
public class T{
int s(int a, int b){return IntStream.range(a,b+1).boxed().map(F::new).sorted(java.util.Comparator.comparingInt(F::getV)).collect(java.util.stream.Collectors.toList()).get(0).i;}}
``````

Ungolfed:

``````import java.util.stream.*;
import java.math.*;

class F {
int v;
int i;
public int getV() { return v; }
F (int i) {
this.i = i;
v = IntStream.range(2,i+1)
.map( j -> ((i%j==0) &&
new BigInteger(""+j).isProbablePrime(1))?j:0)
.max()
.getAsInt();
}
}

public class T {
int s(int a, int b) {
return IntStream.range(a,b+1)
.boxed()
.map(F::new)
.sorted(java.util.Comparator.comparingInt(F::getV))
.collect(java.util.stream.Collectors.toList())
.get(0).i;
}
}
``````

example run using:

``````public static void main(String[] s) {
System.out.println(new T().s(157,249));
}

192
``````
-

# C#, 240234226 161 characters

``````int S(int i,int b){int s=2<<29,n=0,k,j,p;for(k=i;i<b;k=++i){for(;k>1;--k){if(i%k<1){p=1;for(j=2;j<k;++j)if(k%j<1)p=0;if(p>0)break;}}if(k<s){s=k;n=i;}}return n;}}
``````

Acknowledgements & Reduction Explanations
- Thanks to CodesInChaos for reductions to 226, see comments for specifics
- Reduced to 161 after re-reading the rules and seeing that a mere function is allowed (i.e., a free-standing program is not required.)

Usage
function:
- input: two integers
- output: if multiple valid answers exist, returns the smallest

Explanation (with comments and runnable test-wrapper)

``````class Test
{
int S(int i, int b)
{
//s = lowest gpf found so far
//n = best answer so far
//i = range iterator
//p = prime indicator (1=true, 0=false)
int s = 2 << 29, n = 0, k, j, p;
for(k=i; i<b; k=++i)
{
//iterate through the factors of i
for(;k>1;--k)
{
if (i % k < 1)
{
p=1;
//determine if k is prime
for (j = 2; j < k; ++j)
if (k % j < 1)
p = 0;
if (p>0) break;
}
}
if (k < s)
{
s = k;
n = i;
}
}
return n;
}

public static void Main(string[] args)
{
var d = new D();
System.Diagnostics.Debug.Assert(d.S(5, 11) == 8);
System.Diagnostics.Debug.Assert(d.S(9, 16) == 9);
System.Diagnostics.Debug.Assert(d.S(9, 17) == 16);
System.Diagnostics.Debug.Assert(d.S(157, 249) == 162);
System.Diagnostics.Debug.Assert(d.S(2001, 2014) == 2002);
}
}
``````
-
Why `using System`? As far as I can tell, you're only using it once, a qualified name `System.Console.Write` should be shorter. – CodesInChaos Aug 21 '14 at 15:55
thanks @CodesInChaos. In my early iterations, I used System for 3 things, then forgot to cleanup after eliminating the other 2. Code updated. – Richard II Aug 21 '14 at 16:01
Turing `p` into an int should save 6 chars. – CodesInChaos Aug 21 '14 at 16:20
yes @CodesInChaos, that thought also occurred to me over the weekend, and just hadn't gotten around to posting an update. – Richard II Aug 25 '14 at 15:36
reduced to 161 by changing from a command-line app to a simple method (after re-reading the rules) – Richard II Aug 28 '14 at 22:17

# MATL (non-competitive), 20 bytes

This language was designed after the challenge

Range is inclusive at both ends. The numbers are taken as two separate inputs.

``````2\$:t[]w"@YfX>v]4#X<)
``````

Try it online!

### Explanation

``````2\$:          % implicitly input two numbers. Inclusive range
t            % duplicate
[]           % empty array
w            % swap elements in stack
"            % for each
@          %   push loop variable
Yf         %   prime factors
X>         %   maximum value
v          %   vertical concatenation
]            % end for each
4#X<         % arg min
)            % index with this arg min into initial range of numbers
``````
-