Composite Factor Soup
$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.
code-golf primes
edited May 10 at 4:37
Xcali
5,910523
asked May 10 at 3:38
don brightdon bright
904614
$endgroup$
add a comment |
$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.
code-golf primes
edited May 10 at 4:37
Xcali
5,910523
asked May 10 at 3:38
don brightdon bright
904614
$endgroup$
13
$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
add a comment |
$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.
code-golf primes
edited May 10 at 4:37
Xcali
5,910523
asked May 10 at 3:38
don brightdon bright
904614
$endgroup$
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.
code-golf primes
code-golf primes
edited May 10 at 4:37
Xcali
5,910523
asked May 10 at 3:38
don brightdon bright
904614
edited May 10 at 4:37
Xcali
5,910523
asked May 10 at 3:38
don brightdon bright
904614
edited May 10 at 4:37
Xcali
5,910523
edited May 10 at 4:37
Xcali
5,910523
edited May 10 at 4:37
Xcali
5,910523
5,910523
asked May 10 at 3:38
don brightdon bright
904614
asked May 10 at 3:38
don brightdon bright
904614
asked May 10 at 3:38
don brightdon bright
904614
904614
13
$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
add a comment |
13
$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
13
13
$begingroup$
Isn't this just the largest prime below n/2?
$endgroup$
– xnor
May 10 at 4:42
$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, 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
$begingroup$
xnor probably... but can it be proven?
$endgroup$
– don bright
May 10 at 23:27
1
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
$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
add a comment |
10 Answers
10
active
oldest
votes
$begingroup$
Neim, 3 bytes
ᚺ>:
Explanation:
ᚺ halve
> increment
: previous prime
Try it online!
answered May 10 at 7:16
OkxOkx
13.1k129103
$endgroup$
add a comment |
$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 $leqfrac{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)
answered May 10 at 6:39
Kevin CruijssenKevin Cruijssen
45.1k576227
$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$
– Grimy
May 10 at 12:30
$begingroup$
@Grimy;>ÅMwas my original answer, which failed for21(resulting in11instead of7). 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
add a comment |
$begingroup$
Wolfram Language (Mathematica), 19 bytes
Prime@PrimePi[#/2]&
Try it online!
answered May 10 at 4:01
attinatattinat
1,05717
$endgroup$
add a comment |
$begingroup$
Japt v1.4.5 -h, 6 bytes
z o fj
Try it
answered May 10 at 4:25
Embodiment of IgnoranceEmbodiment of Ignorance
3,874128
$endgroup$
add a comment |
$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
answered May 10 at 6:43
Galen IvanovGalen Ivanov
8,35711237
$endgroup$
$begingroup$
@Arnauld Thank you for finding the bug. Fixed.
$endgroup$
– Galen Ivanov
May 10 at 12:24
add a comment |
$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
answered May 10 at 5:57
Nick KennedyNick Kennedy
2,65469
$endgroup$
add a comment |
$begingroup$
Factor, 37 bytes
: p ( n -- n ) 2 / primes-upto last ;
Try it online!
answered May 10 at 12:36
Galen IvanovGalen Ivanov
8,35711237
$endgroup$
add a comment |
$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 $pleleftlfloordfrac{n}{2}rightrfloor$.
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)
answered May 10 at 11:40
ArnauldArnauld
85.1k7100349
$endgroup$
add a comment |
$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.
answered May 10 at 12:24
NeilNeil
84.6k845183
$endgroup$
1
$begingroup$
-2 bytes
$endgroup$
– Grimy
May 10 at 12:40
add a comment |
$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!
answered May 10 at 20:28
Value InkValue Ink
8,205731
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f185381%2fcomposite-factor-soup%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
10 Answers
10
active
oldest
votes
10 Answers
10
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Neim, 3 bytes
ᚺ>:
Explanation:
ᚺ halve
> increment
: previous prime
Try it online!
answered May 10 at 7:16
OkxOkx
13.1k129103
$endgroup$
add a comment |
$begingroup$
Neim, 3 bytes
ᚺ>:
Explanation:
ᚺ halve
> increment
: previous prime
Try it online!
answered May 10 at 7:16
OkxOkx
13.1k129103
$endgroup$
add a comment |
$begingroup$
Neim, 3 bytes
ᚺ>:
Explanation:
ᚺ halve
> increment
: previous prime
Try it online!
answered May 10 at 7:16
OkxOkx
13.1k129103
$endgroup$
Neim, 3 bytes
ᚺ>:
Explanation:
ᚺ halve
> increment
: previous prime
Try it online!
answered May 10 at 7:16
OkxOkx
13.1k129103
answered May 10 at 7:16
OkxOkx
13.1k129103
answered May 10 at 7:16
OkxOkx
13.1k129103
answered May 10 at 7:16
OkxOkx
13.1k129103
13.1k129103
add a comment |
add a comment |
$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 $leqfrac{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)
answered May 10 at 6:39
Kevin CruijssenKevin Cruijssen
45.1k576227
$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$
– Grimy
May 10 at 12:30
$begingroup$
@Grimy;>ÅMwas my original answer, which failed for21(resulting in11instead of7). 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
add a comment |
$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 $leqfrac{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)
answered May 10 at 6:39
Kevin CruijssenKevin Cruijssen
45.1k576227
$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$
– Grimy
May 10 at 12:30
$begingroup$
@Grimy;>ÅMwas my original answer, which failed for21(resulting in11instead of7). 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
add a comment |
$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 $leqfrac{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)
answered May 10 at 6:39
Kevin CruijssenKevin Cruijssen
45.1k576227
$endgroup$
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 $leqfrac{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)
answered May 10 at 6:39
Kevin CruijssenKevin Cruijssen
45.1k576227
edited May 10 at 12:37
answered May 10 at 6:39
Kevin CruijssenKevin Cruijssen
45.1k576227
answered May 10 at 6:39
Kevin CruijssenKevin Cruijssen
45.1k576227
answered May 10 at 6:39
Kevin CruijssenKevin Cruijssen
45.1k576227
45.1k576227
$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$
– Grimy
May 10 at 12:30
$begingroup$
@Grimy;>ÅMwas my original answer, which failed for21(resulting in11instead of7). 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
add a comment |
$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$
– Grimy
May 10 at 12:30
$begingroup$
@Grimy;>ÅMwas my original answer, which failed for21(resulting in11instead of7). 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
$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$
– Grimy
May 10 at 12:30
$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$
– Grimy
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$
@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
$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
add a comment |
$begingroup$
Wolfram Language (Mathematica), 19 bytes
Prime@PrimePi[#/2]&
Try it online!
answered May 10 at 4:01
attinatattinat
1,05717
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 19 bytes
Prime@PrimePi[#/2]&
Try it online!
answered May 10 at 4:01
attinatattinat
1,05717
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 19 bytes
Prime@PrimePi[#/2]&
Try it online!
answered May 10 at 4:01
attinatattinat
1,05717
$endgroup$
Wolfram Language (Mathematica), 19 bytes
Prime@PrimePi[#/2]&
Try it online!
answered May 10 at 4:01
attinatattinat
1,05717
edited May 10 at 4:08
answered May 10 at 4:01
attinatattinat
1,05717
answered May 10 at 4:01
attinatattinat
1,05717
answered May 10 at 4:01
attinatattinat
1,05717
1,05717
add a comment |
add a comment |
$begingroup$
Japt v1.4.5 -h, 6 bytes
z o fj
Try it
answered May 10 at 4:25
Embodiment of IgnoranceEmbodiment of Ignorance
3,874128
$endgroup$
add a comment |
$begingroup$
Japt v1.4.5 -h, 6 bytes
z o fj
Try it
answered May 10 at 4:25
Embodiment of IgnoranceEmbodiment of Ignorance
3,874128
$endgroup$
add a comment |
$begingroup$
Japt v1.4.5 -h, 6 bytes
z o fj
Try it
answered May 10 at 4:25
Embodiment of IgnoranceEmbodiment of Ignorance
3,874128
$endgroup$
Japt v1.4.5 -h, 6 bytes
z o fj
Try it
answered May 10 at 4:25
Embodiment of IgnoranceEmbodiment of Ignorance
3,874128
edited May 10 at 4:52
answered May 10 at 4:25
Embodiment of IgnoranceEmbodiment of Ignorance
3,874128
answered May 10 at 4:25
Embodiment of IgnoranceEmbodiment of Ignorance
3,874128
answered May 10 at 4:25
Embodiment of IgnoranceEmbodiment of Ignorance
3,874128
3,874128
add a comment |
add a comment |
$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
answered May 10 at 6:43
Galen IvanovGalen Ivanov
8,35711237
$endgroup$
$begingroup$
@Arnauld Thank you for finding the bug. Fixed.
$endgroup$
– Galen Ivanov
May 10 at 12:24
add a comment |
$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
answered May 10 at 6:43
Galen IvanovGalen Ivanov
8,35711237
$endgroup$
$begingroup$
@Arnauld Thank you for finding the bug. Fixed.
$endgroup$
– Galen Ivanov
May 10 at 12:24
add a comment |
$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
answered May 10 at 6:43
Galen IvanovGalen Ivanov
8,35711237
$endgroup$
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
answered May 10 at 6:43
Galen IvanovGalen Ivanov
8,35711237
edited May 10 at 12:23
answered May 10 at 6:43
Galen IvanovGalen Ivanov
8,35711237
answered May 10 at 6:43
Galen IvanovGalen Ivanov
8,35711237
answered May 10 at 6:43
Galen IvanovGalen Ivanov
8,35711237
8,35711237
$begingroup$
@Arnauld Thank you for finding the bug. Fixed.
$endgroup$
– Galen Ivanov
May 10 at 12:24
add a comment |
$begingroup$
@Arnauld Thank you for finding the bug. Fixed.
$endgroup$
– Galen Ivanov
May 10 at 12:24
$begingroup$
@Arnauld Thank you for finding the bug. Fixed.
$endgroup$
– Galen Ivanov
May 10 at 12:24
$begingroup$
@Arnauld Thank you for finding the bug. Fixed.
$endgroup$
– Galen Ivanov
May 10 at 12:24
add a comment |
$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
answered May 10 at 5:57
Nick KennedyNick Kennedy
2,65469
$endgroup$
add a comment |
$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
answered May 10 at 5:57
Nick KennedyNick Kennedy
2,65469
$endgroup$
add a comment |
$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
answered May 10 at 5:57
Nick KennedyNick Kennedy
2,65469
$endgroup$
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
answered May 10 at 5:57
Nick KennedyNick Kennedy
2,65469
edited May 10 at 12:25
answered May 10 at 5:57
Nick KennedyNick Kennedy
2,65469
answered May 10 at 5:57
Nick KennedyNick Kennedy
2,65469
answered May 10 at 5:57
Nick KennedyNick Kennedy
2,65469
2,65469
add a comment |
add a comment |
$begingroup$
Factor, 37 bytes
: p ( n -- n ) 2 / primes-upto last ;
Try it online!
answered May 10 at 12:36
Galen IvanovGalen Ivanov
8,35711237
$endgroup$
add a comment |
$begingroup$
Factor, 37 bytes
: p ( n -- n ) 2 / primes-upto last ;
Try it online!
answered May 10 at 12:36
Galen IvanovGalen Ivanov
8,35711237
$endgroup$
add a comment |
$begingroup$
Factor, 37 bytes
: p ( n -- n ) 2 / primes-upto last ;
Try it online!
answered May 10 at 12:36
Galen IvanovGalen Ivanov
8,35711237
$endgroup$
Factor, 37 bytes
: p ( n -- n ) 2 / primes-upto last ;
Try it online!
answered May 10 at 12:36
Galen IvanovGalen Ivanov
8,35711237
answered May 10 at 12:36
Galen IvanovGalen Ivanov
8,35711237
answered May 10 at 12:36
Galen IvanovGalen Ivanov
8,35711237
answered May 10 at 12:36
Galen IvanovGalen Ivanov
8,35711237
8,35711237
add a comment |
add a comment |
$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 $pleleftlfloordfrac{n}{2}rightrfloor$.
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)
answered May 10 at 11:40
ArnauldArnauld
85.1k7100349
$endgroup$
add a comment |
$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 $pleleftlfloordfrac{n}{2}rightrfloor$.
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)
answered May 10 at 11:40
ArnauldArnauld
85.1k7100349
$endgroup$
add a comment |
$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 $pleleftlfloordfrac{n}{2}rightrfloor$.
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)
answered May 10 at 11:40
ArnauldArnauld
85.1k7100349
$endgroup$
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 $pleleftlfloordfrac{n}{2}rightrfloor$.
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)
answered May 10 at 11:40
ArnauldArnauld
85.1k7100349
edited May 10 at 12:51
answered May 10 at 11:40
ArnauldArnauld
85.1k7100349
answered May 10 at 11:40
ArnauldArnauld
85.1k7100349
answered May 10 at 11:40
ArnauldArnauld
85.1k7100349
85.1k7100349
add a comment |
add a comment |
$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.
answered May 10 at 12:24
NeilNeil
84.6k845183
$endgroup$
1
$begingroup$
-2 bytes
$endgroup$
– Grimy
May 10 at 12:40
add a comment |
$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.
answered May 10 at 12:24
NeilNeil
84.6k845183
$endgroup$
1
$begingroup$
-2 bytes
$endgroup$
– Grimy
May 10 at 12:40
add a comment |
$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.
answered May 10 at 12:24
NeilNeil
84.6k845183
$endgroup$
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.
answered May 10 at 12:24
NeilNeil
84.6k845183
edited May 10 at 13:11
answered May 10 at 12:24
NeilNeil
84.6k845183
answered May 10 at 12:24
NeilNeil
84.6k845183
answered May 10 at 12:24
NeilNeil
84.6k845183
84.6k845183
1
$begingroup$
-2 bytes
$endgroup$
– Grimy
May 10 at 12:40
add a comment |
1
$begingroup$
-2 bytes
$endgroup$
– Grimy
May 10 at 12:40
1
1
$begingroup$
-2 bytes
$endgroup$
– Grimy
May 10 at 12:40
$begingroup$
-2 bytes
$endgroup$
– Grimy
May 10 at 12:40
add a comment |
$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!
answered May 10 at 20:28
Value InkValue Ink
8,205731
$endgroup$
add a comment |
$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!
answered May 10 at 20:28
Value InkValue Ink
8,205731
$endgroup$
add a comment |
$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!
answered May 10 at 20:28
Value InkValue Ink
8,205731
$endgroup$
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!
answered May 10 at 20:28
Value InkValue Ink
8,205731
answered May 10 at 20:28
Value InkValue Ink
8,205731
answered May 10 at 20:28
Value InkValue Ink
8,205731
answered May 10 at 20:28
Value InkValue Ink
8,205731
8,205731
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f185381%2fcomposite-factor-soup%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
13
$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