Composite Factor Soup

Question

Per the fundamental theorem of arithmetic, for a given number \$n\$, it is possible to find it's prime factors, and they are unique. Let's imagine we talk only of \$n\$ that is non-prime (composite).

We can also find the factors of all the composite numbers smaller than \$n\$. For example if \$n\$ is 10, then it has factors 5 and 2. 9 has 3 and 3. 8 has 2, thrice. 6 has 3 and 2. 4 has 2 and 2. So for the number 10, all the prime factors of all the composite numbers smaller than 10 would be listed as 2,3, and 5.

Now if you put a lot of vegetables in a pot for soup, often the largest will rise to the top. So if we put all of these factors in a big pot, which one will be the largest and rise to the top? For 10 soup, that answer is 5.

"Silly", you might think, "the number \$n\$ itself will have the largest factors, larger than the factors of numbers smaller than \$n\$". But this is where you are wrong my friend!

For example, the factors of 16 are all 2, repeated four times. The factors of 15 are 5 and 3, now, I don't have to be a mathematician to tell that 15 is smaller than 16, but 5 is bigger than 2!

Your challenge is to explore how this works for bigger \$n\$. For any number given input number \$n\$, assumed natural, composite, and less than 2^32, find out which is the "largest factor" of all the prime factors of all the composite numbers less than or equal to \$n\$.

Good luck and have fun!

Smallest byte count wins.

Answer 1

Neim, 3 bytes

ᚺ>:

Explanation:

ᚺ   halve
 >  increment
  : previous prime

Try it online!

Answer 2

05AB1E, 4 bytes

;ÅPθ

Try it online or verify first \$[4,n]\$ numbers.

Explanation:

Implementation of the observation @xnor's made in his comment: largest prime \$\leq\frac{1}{2}n\$. Which I've literally implemented now (after @Arnauld reported some bugs in my initial program):

;     # Halve the (implicit) input
 ÅP   # Get a list of primes smaller than or equal to this
   à  # And only leave the largest prime
      # (which is output implicitly as result)

Answer 3

Wolfram Language (Mathematica), 19 bytes

Prime@PrimePi[#/2]&

Try it online!

Answer 4

Japt v1.4.5 -h, 6 bytes

z o fj

Try it

Answer 5

J, 10 bytes

_4 p:-:@>:

Try it online!

Uses the xnor's observation

Explanation:

_4 p:       the next prime smaller than 
        >:  the input  plus 1
     -:@    divided by 2

Answer 6

Jelly, 4 bytes

‘HÆp

Try it online!

As others have observed, the answer is the largest prime \$≤ n/2\$

Thanks to @Arnauld for correcting my order of halving/incrementing

Answer 7

Factor, 37 bytes

: p ( n -- n ) 2 / primes-upto last ;

Try it online!

Answer 8

JavaScript (ES6), 40 bytes

After a careful analysis of (xnor's comment on) the challenge, it turns out that  42 41  40 is the answer.

n=>(g=k=>n%--k?g(k):k<2?n:g(--n))(n>>=1)

Try it online!

Commented

We look for the highest prime \$p\le\left\lfloor\dfrac{n}{2}\right\rfloor\$.

n => (          // n = input
  g = k =>      // g = recursive function looking for the highest divisor k < n of n
    n % --k ?   //   decrement k; if k is not a divisor of n:
      g(k)      //     do recursive calls until it is
    :           //   else:
      k < 2 ?   //     if k is less than 2 (i.e. n is prime):
        n       //       stop recursion and return n
      :         //     else:
        g(--n)  //       try again with n - 1
  )(n >>= 1)    // initial call to g with n = floor(n / 2)

Answer 9

Retina 0.8.2, 34 32 bytes

.+
$*
(.+)(?<!^\2+(..+))\1.*
$.1

Try it online! Edit: Saved 2 bytes thanks to @Grimy. Explanation:

.+
$*

Convert to unary.

(.+)

Find the largest number...

(?<!^\2+(..+))

... that is prime ...

\1.*

... and a factor of a number not greater than the input.

$.1

Convert to decimal.

Answer 10

Ruby, 24+8 = 32 bytes

8 bytes for the -rprime flag (plus space) to import the Prime module. Prime.each(n) gets all primes up to n, then we just take the largest one. (We could take the last item since it's in order, but that costs more bytes.)

->n{Prime.each(n/2).max}

Try it online!

Answer 11

Husk, 7 bytes

→`↑İp≤½

Try it online!