3
\$\begingroup\$

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.

\$\endgroup\$
  • 14
    \$\begingroup\$ Isn't this just the largest prime below n/2? \$\endgroup\$ – xnor May 10 at 4:42
  • \$\begingroup\$ xnor, Could it be the largest prime below or up to and including n/2? That would fit the '10' example in the question. \$\endgroup\$ – ouflak May 10 at 12:48
  • \$\begingroup\$ xnor probably... but can it be proven? \$\endgroup\$ – don bright May 10 at 23:27
  • 1
    \$\begingroup\$ The proof is easy. The smallest composite number given some prime $p$ is $2p$. Therefore, a larger prime than $n/2$ cannot give a composite number less or equal to $n$ (upper bound). Conversely, the largest prime less or equal to $n/2$ will give have at least one composite number less or equal to $n$, namely, $2p$ (existence) \$\endgroup\$ – Sanchises May 11 at 10:30

10 Answers 10

7
\$\begingroup\$

Neim, 3 bytes

ᚺ>:

Explanation:

ᚺ   halve
 >  increment
  : previous prime

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ This doesn't work: it returns 2 instead of 3 for input 7, and fails similarly for any number that's 2 * a prime + 1. Removing the < fixes it. \$\endgroup\$ – Grimmy May 10 at 12:30
  • \$\begingroup\$ @Grimy ;>ÅM was my original answer, which failed for 21 (resulting in 11 instead of 7). But it should be fixed now by using ÅP (which is \$\leq\$) instead of ÅM (which is \$\lt\$). \$\endgroup\$ – Kevin Cruijssen May 10 at 12:32
  • \$\begingroup\$ Yes it is. :) (According to the spec, you should only consider composite inputs in \$[4,n]\$ but it doesn't really matter.) \$\endgroup\$ – Arnauld May 10 at 12:34
2
\$\begingroup\$

Wolfram Language (Mathematica), 19 bytes

Prime@PrimePi[#/2]&

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Japt v1.4.5 -h, 6 bytes

z o fj

Try it

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @Arnauld Thank you for finding the bug. Fixed. \$\endgroup\$ – Galen Ivanov May 10 at 12:24
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Factor, 37 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ -2 bytes \$\endgroup\$ – Grimmy May 10 at 12:40
2
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.