Mixing
Identifying all prime numbers less than 200
$begingroup$
Below is the question I am confused on. I will provide my logic to my solution also.
In order to identify all the prime numbers less than 200, a person writes each number from 1 to 200, and eliminates all the multiples of 2, then all the multiples of 3. To complete this task, the person will have to eliminate the multiples of which additional numbers?
A. 5, 7, 9, 11
B. 7, 9, 11, 13
C. 5, 7, 11, 13
D. 7, 11, 13, 17
I eliminated answer choices A and B, since all multiples of 9, will ALSO be multiples of 3. So the person does not have to repeat the process over. I also eliminated answer choice C, since all multiples of 10, are also multiples of 5, which are also multiples of 2 (i.e. 10, 20, 30, 40, 50 etc.) Again, the person would not need to repeat the process over. So I chose answer D. However, the correct answer is C.
number-theory prime-numbers
edited Jun 20 '17 at 5:56
dxiv
58.1k648102
asked Jun 20 '17 at 5:44
Akhil RamanAkhil Raman
192
$endgroup$
add a comment |
$begingroup$
Below is the question I am confused on. I will provide my logic to my solution also.
In order to identify all the prime numbers less than 200, a person writes each number from 1 to 200, and eliminates all the multiples of 2, then all the multiples of 3. To complete this task, the person will have to eliminate the multiples of which additional numbers?
A. 5, 7, 9, 11
B. 7, 9, 11, 13
C. 5, 7, 11, 13
D. 7, 11, 13, 17
I eliminated answer choices A and B, since all multiples of 9, will ALSO be multiples of 3. So the person does not have to repeat the process over. I also eliminated answer choice C, since all multiples of 10, are also multiples of 5, which are also multiples of 2 (i.e. 10, 20, 30, 40, 50 etc.) Again, the person would not need to repeat the process over. So I chose answer D. However, the correct answer is C.
number-theory prime-numbers
edited Jun 20 '17 at 5:56
dxiv
58.1k648102
asked Jun 20 '17 at 5:44
Akhil RamanAkhil Raman
192
$endgroup$
2
$begingroup$
With D how do you eliminate 25?
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 5:47
1
$begingroup$
Lord Shark the Unknown, 25 is not a prime number. ( 5 x 5 = 25).
$endgroup$
– Akhil Raman
Jun 20 '17 at 6:04
1
$begingroup$
Exactly, that is why it has to be eliminated!
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 6:06
add a comment |
$begingroup$
Below is the question I am confused on. I will provide my logic to my solution also.
In order to identify all the prime numbers less than 200, a person writes each number from 1 to 200, and eliminates all the multiples of 2, then all the multiples of 3. To complete this task, the person will have to eliminate the multiples of which additional numbers?
A. 5, 7, 9, 11
B. 7, 9, 11, 13
C. 5, 7, 11, 13
D. 7, 11, 13, 17
I eliminated answer choices A and B, since all multiples of 9, will ALSO be multiples of 3. So the person does not have to repeat the process over. I also eliminated answer choice C, since all multiples of 10, are also multiples of 5, which are also multiples of 2 (i.e. 10, 20, 30, 40, 50 etc.) Again, the person would not need to repeat the process over. So I chose answer D. However, the correct answer is C.
number-theory prime-numbers
edited Jun 20 '17 at 5:56
dxiv
58.1k648102
asked Jun 20 '17 at 5:44
Akhil RamanAkhil Raman
192
$endgroup$
Below is the question I am confused on. I will provide my logic to my solution also.
In order to identify all the prime numbers less than 200, a person writes each number from 1 to 200, and eliminates all the multiples of 2, then all the multiples of 3. To complete this task, the person will have to eliminate the multiples of which additional numbers?
A. 5, 7, 9, 11
B. 7, 9, 11, 13
C. 5, 7, 11, 13
D. 7, 11, 13, 17
I eliminated answer choices A and B, since all multiples of 9, will ALSO be multiples of 3. So the person does not have to repeat the process over. I also eliminated answer choice C, since all multiples of 10, are also multiples of 5, which are also multiples of 2 (i.e. 10, 20, 30, 40, 50 etc.) Again, the person would not need to repeat the process over. So I chose answer D. However, the correct answer is C.
number-theory prime-numbers
number-theory prime-numbers
edited Jun 20 '17 at 5:56
dxiv
58.1k648102
asked Jun 20 '17 at 5:44
Akhil RamanAkhil Raman
192
edited Jun 20 '17 at 5:56
dxiv
58.1k648102
asked Jun 20 '17 at 5:44
Akhil RamanAkhil Raman
192
edited Jun 20 '17 at 5:56
dxiv
58.1k648102
edited Jun 20 '17 at 5:56
dxiv
58.1k648102
edited Jun 20 '17 at 5:56
dxiv
58.1k648102
58.1k648102
asked Jun 20 '17 at 5:44
Akhil RamanAkhil Raman
192
asked Jun 20 '17 at 5:44
Akhil RamanAkhil Raman
192
asked Jun 20 '17 at 5:44
Akhil RamanAkhil Raman
192
192
2
$begingroup$
With D how do you eliminate 25?
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 5:47
1
$begingroup$
Lord Shark the Unknown, 25 is not a prime number. ( 5 x 5 = 25).
$endgroup$
– Akhil Raman
Jun 20 '17 at 6:04
1
$begingroup$
Exactly, that is why it has to be eliminated!
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 6:06
add a comment |
2
$begingroup$
With D how do you eliminate 25?
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 5:47
1
$begingroup$
Lord Shark the Unknown, 25 is not a prime number. ( 5 x 5 = 25).
$endgroup$
– Akhil Raman
Jun 20 '17 at 6:04
1
$begingroup$
Exactly, that is why it has to be eliminated!
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 6:06
2
2
$begingroup$
With D how do you eliminate 25?
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 5:47
$begingroup$
With D how do you eliminate 25?
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 5:47
1
1
$begingroup$
Lord Shark the Unknown, 25 is not a prime number. ( 5 x 5 = 25).
$endgroup$
– Akhil Raman
Jun 20 '17 at 6:04
$begingroup$
Lord Shark the Unknown, 25 is not a prime number. ( 5 x 5 = 25).
$endgroup$
– Akhil Raman
Jun 20 '17 at 6:04
1
1
$begingroup$
Exactly, that is why it has to be eliminated!
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 6:06
$begingroup$
Exactly, that is why it has to be eliminated!
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 6:06
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
By always eliminating multiples of numbers you can guarantee that you only have to remove multiples of prime numbers (as you noted, you have already removed all multiples of 9 by removing all multiples of 3). So the remaining issue is how large a prime number you have to reach before you've eliminated all the possible composite numbers.
Any composite (non-prime) number must have at least two factors, neither of which is one, e.g. $169 = 13 times 13$, and those factors must be either equal, or one is larger than the other. These numbers will always be eliminated when we remove the multiples of the smaller factor (e.g. $161 = 7 times 23$ will be eliminated when we remove multiples of $7$ and so is gone when we reach multiples of $23$).
So, we can always stop when we reach the largest prime number smaller than the square root of the limit -- in this case, when we reach the largest prime number smaller than $sqrt{200}$. (The square root, say $a$ has the property that $atimes a = 200$ so any other combination of factors must have one larger, one smaller).
$13times 13 = 169 < 200$ and $17times 17 = 289 > 200$, so we don't need to check as far as $17$ and D cannot be the answer, which leaves C.
answered Jun 20 '17 at 5:55
postmortespostmortes
2,29531422
$endgroup$
add a comment |
$begingroup$
Your reasoning is a bit "in reverse" when you are thinking about the 10. When you employed 2, the 10 & all of its multiples 20, 30, 40, et. al. were indeed eliminated. Note here that 25 was skipped. The fact that 5 is a factor of 10 makes no difference as that 5 never gets used. When actually using this method, its no problem at all to determine what number to use next: it's simply the next higher number not already marked out.
answered Jun 20 '17 at 15:32
Barry KendrickBarry Kendrick
561
$endgroup$
add a comment |
$begingroup$
Doing the sieve with the primes in order, the first nontrivial multiple of $p$ to eliminate is $p^2$.
If $p$ is an odd prime, then $2p$ should have already been eliminated when you were crossing off the multiples of $2$. But $p^2$ is odd, not even, so it shouldn't have been eliminated at a prior step. Likewise, if $p$ is a prime greater than $3$, then you don't need to cross $2p$ and $3p$ off again because they should have already been crossed off.
Let's see what happens with D. You might forget to cross off $35$ if you skip ahead to $49$. And then at the end of the process you might come to the absurd conclusion that both $5$ and $25$, and possibly $35$ and $105$, are also prime, which is of course incorrect.
answered Jun 20 '17 at 21:43
Mr. BrooksMr. Brooks
21111338
$endgroup$
add a comment |
$begingroup$
If $n>1$ and $n$ is not prime then $n=ab$ with $a>1$ and $b>1$ and it cannot be true that both $a$ and $b$ are $>sqrt n.$ So one of $a,b$ is $leq sqrt n$, and will have a prime divisor that is also $leq sqrt n.$
So if $1<nleq 200$ and $n$ is not prime then $n$ is divisible by a prime $pleq sqrt nleq sqrt {200};.$ The largest prime not exceeding $sqrt {200};$ is $13.$
You might also notice that the prime $5$ is not in choice D. Using D would not eliminate $25$ or $125$ from the list of primes.
This method of finding primes is called the Sieve of Erastosthenes.
answered Jun 20 '17 at 22:21
DanielWainfleetDanielWainfleet
35.8k31648
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f2329394%2fidentifying-all-prime-numbers-less-than-200%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
By always eliminating multiples of numbers you can guarantee that you only have to remove multiples of prime numbers (as you noted, you have already removed all multiples of 9 by removing all multiples of 3). So the remaining issue is how large a prime number you have to reach before you've eliminated all the possible composite numbers.
Any composite (non-prime) number must have at least two factors, neither of which is one, e.g. $169 = 13 times 13$, and those factors must be either equal, or one is larger than the other. These numbers will always be eliminated when we remove the multiples of the smaller factor (e.g. $161 = 7 times 23$ will be eliminated when we remove multiples of $7$ and so is gone when we reach multiples of $23$).
So, we can always stop when we reach the largest prime number smaller than the square root of the limit -- in this case, when we reach the largest prime number smaller than $sqrt{200}$. (The square root, say $a$ has the property that $atimes a = 200$ so any other combination of factors must have one larger, one smaller).
$13times 13 = 169 < 200$ and $17times 17 = 289 > 200$, so we don't need to check as far as $17$ and D cannot be the answer, which leaves C.
answered Jun 20 '17 at 5:55
postmortespostmortes
2,29531422
$endgroup$
add a comment |
$begingroup$
By always eliminating multiples of numbers you can guarantee that you only have to remove multiples of prime numbers (as you noted, you have already removed all multiples of 9 by removing all multiples of 3). So the remaining issue is how large a prime number you have to reach before you've eliminated all the possible composite numbers.
Any composite (non-prime) number must have at least two factors, neither of which is one, e.g. $169 = 13 times 13$, and those factors must be either equal, or one is larger than the other. These numbers will always be eliminated when we remove the multiples of the smaller factor (e.g. $161 = 7 times 23$ will be eliminated when we remove multiples of $7$ and so is gone when we reach multiples of $23$).
So, we can always stop when we reach the largest prime number smaller than the square root of the limit -- in this case, when we reach the largest prime number smaller than $sqrt{200}$. (The square root, say $a$ has the property that $atimes a = 200$ so any other combination of factors must have one larger, one smaller).
$13times 13 = 169 < 200$ and $17times 17 = 289 > 200$, so we don't need to check as far as $17$ and D cannot be the answer, which leaves C.
answered Jun 20 '17 at 5:55
postmortespostmortes
2,29531422
$endgroup$
add a comment |
$begingroup$
By always eliminating multiples of numbers you can guarantee that you only have to remove multiples of prime numbers (as you noted, you have already removed all multiples of 9 by removing all multiples of 3). So the remaining issue is how large a prime number you have to reach before you've eliminated all the possible composite numbers.
Any composite (non-prime) number must have at least two factors, neither of which is one, e.g. $169 = 13 times 13$, and those factors must be either equal, or one is larger than the other. These numbers will always be eliminated when we remove the multiples of the smaller factor (e.g. $161 = 7 times 23$ will be eliminated when we remove multiples of $7$ and so is gone when we reach multiples of $23$).
So, we can always stop when we reach the largest prime number smaller than the square root of the limit -- in this case, when we reach the largest prime number smaller than $sqrt{200}$. (The square root, say $a$ has the property that $atimes a = 200$ so any other combination of factors must have one larger, one smaller).
$13times 13 = 169 < 200$ and $17times 17 = 289 > 200$, so we don't need to check as far as $17$ and D cannot be the answer, which leaves C.
answered Jun 20 '17 at 5:55
postmortespostmortes
2,29531422
$endgroup$
By always eliminating multiples of numbers you can guarantee that you only have to remove multiples of prime numbers (as you noted, you have already removed all multiples of 9 by removing all multiples of 3). So the remaining issue is how large a prime number you have to reach before you've eliminated all the possible composite numbers.
Any composite (non-prime) number must have at least two factors, neither of which is one, e.g. $169 = 13 times 13$, and those factors must be either equal, or one is larger than the other. These numbers will always be eliminated when we remove the multiples of the smaller factor (e.g. $161 = 7 times 23$ will be eliminated when we remove multiples of $7$ and so is gone when we reach multiples of $23$).
So, we can always stop when we reach the largest prime number smaller than the square root of the limit -- in this case, when we reach the largest prime number smaller than $sqrt{200}$. (The square root, say $a$ has the property that $atimes a = 200$ so any other combination of factors must have one larger, one smaller).
$13times 13 = 169 < 200$ and $17times 17 = 289 > 200$, so we don't need to check as far as $17$ and D cannot be the answer, which leaves C.
answered Jun 20 '17 at 5:55
postmortespostmortes
2,29531422
answered Jun 20 '17 at 5:55
postmortespostmortes
2,29531422
answered Jun 20 '17 at 5:55
postmortespostmortes
2,29531422
answered Jun 20 '17 at 5:55
postmortespostmortes
2,29531422
2,29531422
add a comment |
add a comment |
$begingroup$
Your reasoning is a bit "in reverse" when you are thinking about the 10. When you employed 2, the 10 & all of its multiples 20, 30, 40, et. al. were indeed eliminated. Note here that 25 was skipped. The fact that 5 is a factor of 10 makes no difference as that 5 never gets used. When actually using this method, its no problem at all to determine what number to use next: it's simply the next higher number not already marked out.
answered Jun 20 '17 at 15:32
Barry KendrickBarry Kendrick
561
$endgroup$
add a comment |
$begingroup$
Your reasoning is a bit "in reverse" when you are thinking about the 10. When you employed 2, the 10 & all of its multiples 20, 30, 40, et. al. were indeed eliminated. Note here that 25 was skipped. The fact that 5 is a factor of 10 makes no difference as that 5 never gets used. When actually using this method, its no problem at all to determine what number to use next: it's simply the next higher number not already marked out.
answered Jun 20 '17 at 15:32
Barry KendrickBarry Kendrick
561
$endgroup$
add a comment |
$begingroup$
Your reasoning is a bit "in reverse" when you are thinking about the 10. When you employed 2, the 10 & all of its multiples 20, 30, 40, et. al. were indeed eliminated. Note here that 25 was skipped. The fact that 5 is a factor of 10 makes no difference as that 5 never gets used. When actually using this method, its no problem at all to determine what number to use next: it's simply the next higher number not already marked out.
answered Jun 20 '17 at 15:32
Barry KendrickBarry Kendrick
561
$endgroup$
Your reasoning is a bit "in reverse" when you are thinking about the 10. When you employed 2, the 10 & all of its multiples 20, 30, 40, et. al. were indeed eliminated. Note here that 25 was skipped. The fact that 5 is a factor of 10 makes no difference as that 5 never gets used. When actually using this method, its no problem at all to determine what number to use next: it's simply the next higher number not already marked out.
answered Jun 20 '17 at 15:32
Barry KendrickBarry Kendrick
561
answered Jun 20 '17 at 15:32
Barry KendrickBarry Kendrick
561
answered Jun 20 '17 at 15:32
Barry KendrickBarry Kendrick
561
answered Jun 20 '17 at 15:32
Barry KendrickBarry Kendrick
561
561
add a comment |
add a comment |
$begingroup$
Doing the sieve with the primes in order, the first nontrivial multiple of $p$ to eliminate is $p^2$.
If $p$ is an odd prime, then $2p$ should have already been eliminated when you were crossing off the multiples of $2$. But $p^2$ is odd, not even, so it shouldn't have been eliminated at a prior step. Likewise, if $p$ is a prime greater than $3$, then you don't need to cross $2p$ and $3p$ off again because they should have already been crossed off.
Let's see what happens with D. You might forget to cross off $35$ if you skip ahead to $49$. And then at the end of the process you might come to the absurd conclusion that both $5$ and $25$, and possibly $35$ and $105$, are also prime, which is of course incorrect.
answered Jun 20 '17 at 21:43
Mr. BrooksMr. Brooks
21111338
$endgroup$
add a comment |
$begingroup$
Doing the sieve with the primes in order, the first nontrivial multiple of $p$ to eliminate is $p^2$.
If $p$ is an odd prime, then $2p$ should have already been eliminated when you were crossing off the multiples of $2$. But $p^2$ is odd, not even, so it shouldn't have been eliminated at a prior step. Likewise, if $p$ is a prime greater than $3$, then you don't need to cross $2p$ and $3p$ off again because they should have already been crossed off.
Let's see what happens with D. You might forget to cross off $35$ if you skip ahead to $49$. And then at the end of the process you might come to the absurd conclusion that both $5$ and $25$, and possibly $35$ and $105$, are also prime, which is of course incorrect.
answered Jun 20 '17 at 21:43
Mr. BrooksMr. Brooks
21111338
$endgroup$
add a comment |
$begingroup$
Doing the sieve with the primes in order, the first nontrivial multiple of $p$ to eliminate is $p^2$.
If $p$ is an odd prime, then $2p$ should have already been eliminated when you were crossing off the multiples of $2$. But $p^2$ is odd, not even, so it shouldn't have been eliminated at a prior step. Likewise, if $p$ is a prime greater than $3$, then you don't need to cross $2p$ and $3p$ off again because they should have already been crossed off.
Let's see what happens with D. You might forget to cross off $35$ if you skip ahead to $49$. And then at the end of the process you might come to the absurd conclusion that both $5$ and $25$, and possibly $35$ and $105$, are also prime, which is of course incorrect.
answered Jun 20 '17 at 21:43
Mr. BrooksMr. Brooks
21111338
$endgroup$
Doing the sieve with the primes in order, the first nontrivial multiple of $p$ to eliminate is $p^2$.
If $p$ is an odd prime, then $2p$ should have already been eliminated when you were crossing off the multiples of $2$. But $p^2$ is odd, not even, so it shouldn't have been eliminated at a prior step. Likewise, if $p$ is a prime greater than $3$, then you don't need to cross $2p$ and $3p$ off again because they should have already been crossed off.
Let's see what happens with D. You might forget to cross off $35$ if you skip ahead to $49$. And then at the end of the process you might come to the absurd conclusion that both $5$ and $25$, and possibly $35$ and $105$, are also prime, which is of course incorrect.
answered Jun 20 '17 at 21:43
Mr. BrooksMr. Brooks
21111338
answered Jun 20 '17 at 21:43
Mr. BrooksMr. Brooks
21111338
answered Jun 20 '17 at 21:43
Mr. BrooksMr. Brooks
21111338
answered Jun 20 '17 at 21:43
Mr. BrooksMr. Brooks
21111338
21111338
add a comment |
add a comment |
$begingroup$
If $n>1$ and $n$ is not prime then $n=ab$ with $a>1$ and $b>1$ and it cannot be true that both $a$ and $b$ are $>sqrt n.$ So one of $a,b$ is $leq sqrt n$, and will have a prime divisor that is also $leq sqrt n.$
So if $1<nleq 200$ and $n$ is not prime then $n$ is divisible by a prime $pleq sqrt nleq sqrt {200};.$ The largest prime not exceeding $sqrt {200};$ is $13.$
You might also notice that the prime $5$ is not in choice D. Using D would not eliminate $25$ or $125$ from the list of primes.
This method of finding primes is called the Sieve of Erastosthenes.
answered Jun 20 '17 at 22:21
DanielWainfleetDanielWainfleet
35.8k31648
$endgroup$
add a comment |
$begingroup$
If $n>1$ and $n$ is not prime then $n=ab$ with $a>1$ and $b>1$ and it cannot be true that both $a$ and $b$ are $>sqrt n.$ So one of $a,b$ is $leq sqrt n$, and will have a prime divisor that is also $leq sqrt n.$
So if $1<nleq 200$ and $n$ is not prime then $n$ is divisible by a prime $pleq sqrt nleq sqrt {200};.$ The largest prime not exceeding $sqrt {200};$ is $13.$
You might also notice that the prime $5$ is not in choice D. Using D would not eliminate $25$ or $125$ from the list of primes.
This method of finding primes is called the Sieve of Erastosthenes.
answered Jun 20 '17 at 22:21
DanielWainfleetDanielWainfleet
35.8k31648
$endgroup$
add a comment |
$begingroup$
If $n>1$ and $n$ is not prime then $n=ab$ with $a>1$ and $b>1$ and it cannot be true that both $a$ and $b$ are $>sqrt n.$ So one of $a,b$ is $leq sqrt n$, and will have a prime divisor that is also $leq sqrt n.$
So if $1<nleq 200$ and $n$ is not prime then $n$ is divisible by a prime $pleq sqrt nleq sqrt {200};.$ The largest prime not exceeding $sqrt {200};$ is $13.$
You might also notice that the prime $5$ is not in choice D. Using D would not eliminate $25$ or $125$ from the list of primes.
This method of finding primes is called the Sieve of Erastosthenes.
answered Jun 20 '17 at 22:21
DanielWainfleetDanielWainfleet
35.8k31648
$endgroup$
If $n>1$ and $n$ is not prime then $n=ab$ with $a>1$ and $b>1$ and it cannot be true that both $a$ and $b$ are $>sqrt n.$ So one of $a,b$ is $leq sqrt n$, and will have a prime divisor that is also $leq sqrt n.$
So if $1<nleq 200$ and $n$ is not prime then $n$ is divisible by a prime $pleq sqrt nleq sqrt {200};.$ The largest prime not exceeding $sqrt {200};$ is $13.$
You might also notice that the prime $5$ is not in choice D. Using D would not eliminate $25$ or $125$ from the list of primes.
This method of finding primes is called the Sieve of Erastosthenes.
answered Jun 20 '17 at 22:21
DanielWainfleetDanielWainfleet
35.8k31648
answered Jun 20 '17 at 22:21
DanielWainfleetDanielWainfleet
35.8k31648
answered Jun 20 '17 at 22:21
DanielWainfleetDanielWainfleet
35.8k31648
answered Jun 20 '17 at 22:21
DanielWainfleetDanielWainfleet
35.8k31648
35.8k31648
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2fmath.stackexchange.com%2fquestions%2f2329394%2fidentifying-all-prime-numbers-less-than-200%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
2
$begingroup$
With D how do you eliminate 25?
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 5:47
1
$begingroup$
Lord Shark the Unknown, 25 is not a prime number. ( 5 x 5 = 25).
$endgroup$
– Akhil Raman
Jun 20 '17 at 6:04
1
$begingroup$
Exactly, that is why it has to be eliminated!
$endgroup$
– Lord Shark the Unknown
Jun 20 '17 at 6:06