Tests for prime numbers
$begingroup$
I'm told to list the prime numbers from 7 to 150 .
I know how to do it the slow way by one by one checking the numbers till 150. But in an exam condition I can't possibility do that .
Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ?
prime-numbers
asked Feb 29 '16 at 12:27
user307640user307640
8691719
$endgroup$
|
show 3 more comments
$begingroup$
I'm told to list the prime numbers from 7 to 150 .
I know how to do it the slow way by one by one checking the numbers till 150. But in an exam condition I can't possibility do that .
Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ?
prime-numbers
asked Feb 29 '16 at 12:27
user307640user307640
8691719
$endgroup$
10
$begingroup$
en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– Mythomorphic
Feb 29 '16 at 12:29
1
$begingroup$
Check only numbers that are adjacent to multiples of $6$ (for example, $5$ and $7$, $11$ and $13$, etc).
$endgroup$
– barak manos
Feb 29 '16 at 12:31
4
$begingroup$
Is there a possible exam condition where you will be asked to list primes in such an interval?
$endgroup$
– Henning Makholm
Feb 29 '16 at 12:33
1
$begingroup$
There are many prime generating sieves and an entire theory domain.
$endgroup$
– user49763
Feb 29 '16 at 23:24
1
$begingroup$
Probably oral test... I had it once where each student had to move to front of the class and mentioned prime numbers from 1-100. (I remember I got tripped on 91)
$endgroup$
– Andrew T.
Mar 1 '16 at 10:00
|
show 3 more comments
$begingroup$
I'm told to list the prime numbers from 7 to 150 .
I know how to do it the slow way by one by one checking the numbers till 150. But in an exam condition I can't possibility do that .
Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ?
prime-numbers
asked Feb 29 '16 at 12:27
user307640user307640
8691719
$endgroup$
I'm told to list the prime numbers from 7 to 150 .
I know how to do it the slow way by one by one checking the numbers till 150. But in an exam condition I can't possibility do that .
Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ?
prime-numbers
prime-numbers
asked Feb 29 '16 at 12:27
user307640user307640
8691719
asked Feb 29 '16 at 12:27
user307640user307640
8691719
asked Feb 29 '16 at 12:27
user307640user307640
8691719
asked Feb 29 '16 at 12:27
user307640user307640
8691719
asked Feb 29 '16 at 12:27
user307640user307640
8691719
8691719
10
$begingroup$
en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– Mythomorphic
Feb 29 '16 at 12:29
1
$begingroup$
Check only numbers that are adjacent to multiples of $6$ (for example, $5$ and $7$, $11$ and $13$, etc).
$endgroup$
– barak manos
Feb 29 '16 at 12:31
4
$begingroup$
Is there a possible exam condition where you will be asked to list primes in such an interval?
$endgroup$
– Henning Makholm
Feb 29 '16 at 12:33
1
$begingroup$
There are many prime generating sieves and an entire theory domain.
$endgroup$
– user49763
Feb 29 '16 at 23:24
1
$begingroup$
Probably oral test... I had it once where each student had to move to front of the class and mentioned prime numbers from 1-100. (I remember I got tripped on 91)
$endgroup$
– Andrew T.
Mar 1 '16 at 10:00
|
show 3 more comments
10
$begingroup$
en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– Mythomorphic
Feb 29 '16 at 12:29
1
$begingroup$
Check only numbers that are adjacent to multiples of $6$ (for example, $5$ and $7$, $11$ and $13$, etc).
$endgroup$
– barak manos
Feb 29 '16 at 12:31
4
$begingroup$
Is there a possible exam condition where you will be asked to list primes in such an interval?
$endgroup$
– Henning Makholm
Feb 29 '16 at 12:33
1
$begingroup$
There are many prime generating sieves and an entire theory domain.
$endgroup$
– user49763
Feb 29 '16 at 23:24
1
$begingroup$
Probably oral test... I had it once where each student had to move to front of the class and mentioned prime numbers from 1-100. (I remember I got tripped on 91)
$endgroup$
– Andrew T.
Mar 1 '16 at 10:00
10
10
$begingroup$
en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– Mythomorphic
Feb 29 '16 at 12:29
$begingroup$
en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– Mythomorphic
Feb 29 '16 at 12:29
1
1
$begingroup$
Check only numbers that are adjacent to multiples of $6$ (for example, $5$ and $7$, $11$ and $13$, etc).
$endgroup$
– barak manos
Feb 29 '16 at 12:31
$begingroup$
Check only numbers that are adjacent to multiples of $6$ (for example, $5$ and $7$, $11$ and $13$, etc).
$endgroup$
– barak manos
Feb 29 '16 at 12:31
4
4
$begingroup$
Is there a possible exam condition where you will be asked to list primes in such an interval?
$endgroup$
– Henning Makholm
Feb 29 '16 at 12:33
$begingroup$
Is there a possible exam condition where you will be asked to list primes in such an interval?
$endgroup$
– Henning Makholm
Feb 29 '16 at 12:33
1
1
$begingroup$
There are many prime generating sieves and an entire theory domain.
$endgroup$
– user49763
Feb 29 '16 at 23:24
$begingroup$
There are many prime generating sieves and an entire theory domain.
$endgroup$
– user49763
Feb 29 '16 at 23:24
1
1
$begingroup$
Probably oral test... I had it once where each student had to move to front of the class and mentioned prime numbers from 1-100. (I remember I got tripped on 91)
$endgroup$
– Andrew T.
Mar 1 '16 at 10:00
$begingroup$
Probably oral test... I had it once where each student had to move to front of the class and mentioned prime numbers from 1-100. (I remember I got tripped on 91)
$endgroup$
– Andrew T.
Mar 1 '16 at 10:00
|
show 3 more comments
9 Answers
9
active
oldest
votes
$begingroup$
That seems like a silly test question, but you can use the Sieve of Eratosthenes. Start with all numbers from 7 to 150 and start removing multiples of integers greater than 1. Animation from the Wikipedia link:
As for proving a number is prime, it is actually much easier to show that a number is not prime. Maybe you have some more idea of what you might see on a test, but those seem like irritating questions.
edited Feb 29 '16 at 16:36
Barry
2,093717
answered Feb 29 '16 at 12:33
CarserCarser
2,63541027
$endgroup$
12
$begingroup$
Note that you're done with the sieve when you reach the square root of the range, in this case $sqrt{150} approx~ 12$.
$endgroup$
– Daniel R. Collins
Feb 29 '16 at 14:15
$begingroup$
@RemcoGerlich He is correct (actually you want to test to $left lceil{sqrt{x}}right rceil $). See this question: stackoverflow.com/questions/5811151/…
$endgroup$
– Carser
Mar 1 '16 at 13:05
2
$begingroup$
@Jedediyah I assume you mean $lfloor sqrt{x} rfloor$.
$endgroup$
– Travis
Mar 1 '16 at 13:07
$begingroup$
@Travis Good assumption! ;p
$endgroup$
– Carser
Mar 1 '16 at 13:07
$begingroup$
@RemcoGerlich The animation actually does stop finding composite numbers at 11. You can see that after that test all of the remaining numbers are primes, and don't have any multiples that aren't already colored in.
$endgroup$
– Carser
Mar 1 '16 at 13:11
|
show 1 more comment
$begingroup$
The illustrated answer above is cool.
Here is something that might be quicker for you during an exam.
The prime numbers between $7$ and $150$ are all the neighbors of multiples of $6$, except:
- Those that end with $5$
- $49$
- $77$
- $91$
- $119$
- $121$
- $133$
- $143$
So you can simply:
- List all multiples of $6$
- List the two neighbors next to each one of them
- Memorize the ones mentioned above and eliminate them
UPDATE:
Just in order to clarify (and simplify) the method mentioned above.
All you have to do is to write down two lists, one starting from $7$ and the other starting from $11$.
Increment each list by $6$ until $150$, and eliminate the values that you have memorized in advance.
$require{cancel}$
- $small7,13,19,colorred{cancel{25}},31,37,43,colorgreen{cancel{49}},colorred{cancel{55}},61,67,73,79,colorred{cancel{85}},colorgreen{cancel{91}},97,103,109,colorred{cancel{115}},colorgreen{cancel{121}},127,colorgreen{cancel{133}},139,colorred{cancel{145}}$
- $small11,17,23,29,colorred{cancel{35}},41,47,53,59,colorred{cancel{65}},71,colorgreen{cancel{77}},83,89,colorred{cancel{95}},101,107,113,colorgreen{cancel{119}},colorred{cancel{125}},131,137,colorgreen{cancel{143}},149$
answered Feb 29 '16 at 12:43
barak manosbarak manos
38k742103
$endgroup$
5
$begingroup$
Yeah I definitely agree that if you know the range of numbers then it is easier to just memorize the primes in that interval.
$endgroup$
– Carser
Feb 29 '16 at 12:47
$begingroup$
@Jedediyah: Assuming that the range is small of course.
$endgroup$
– barak manos
Feb 29 '16 at 12:48
$begingroup$
@Jedediyah: And in the case above, you can just as well check the divisibility of each number in that range by $2,3,5,7,11$ (out of which, the first three are rather easy).
$endgroup$
– barak manos
Feb 29 '16 at 12:49
1
$begingroup$
For the range, doing the one away from a multiple of six you only need to check divisibility by 5,7,11 Five is obvious 11 almost obvious (there are only 13 of them and the single digit ones are obvious. With these tricks it shouldn't take more than a minute even with being very careful.
$endgroup$
– fleablood
Feb 29 '16 at 16:55
3
$begingroup$
@fleablood: 143 doesn't have smaller factors than 11 :-) I think the problem here is more or less what the questioner suggests in the question: rushing it under stress will cause mistakes, taking it slowly and methodically might take too long. As barak shows it's possible to prepare specifically to list primes up to 150 quickly (heck, you could just memorise the sequence of primes). But if you do that and then you're actually asked to list primes up to 160 quickly then your short-cuts may or may not still be valid.
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:36
|
show 6 more comments
$begingroup$
Given a number $n$.
You need to (1) find all primes smaller than $sqrt{n}$ and (2) see if any of them divides $n$.
If none of them divides $n$ then you have a prime, otherwise it's a composite number.
Example:
Is 147 prime?
$sqrt{147} < 13$ so we have 2, 3, 5, 7, and 11 to check.
3 divides 147 so we don't need to look further.
147 is a composite number.
answered Feb 29 '16 at 14:33
snoramsnoram
454313
$endgroup$
1
$begingroup$
The fact we are building on is that if $n$ is a composite then it has a prime factor smaller than $sqrt{n}$. The proof is easy.
$endgroup$
– snoram
Feb 29 '16 at 14:35
4
$begingroup$
The would take an incredibly long time if you need to do it on every number between 7 and 150 and the OP already knows how to do that. S/he specifically asked for a method to avoid having to check every single number.
$endgroup$
– fleablood
Feb 29 '16 at 16:50
$begingroup$
Agreed it would take long time. But disagree that the question is clear on exactly what is being asked. It ends with two questions "Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ? "
$endgroup$
– snoram
Mar 1 '16 at 7:10
$begingroup$
My answer addresses both questions.
$endgroup$
– snoram
Mar 1 '16 at 9:27
add a comment |
$begingroup$
My favorite mnemonic:
91 is the only number less than 100 that looks like a prime and isn't.
That's because these numbers don't look like primes: evens, multiples of 5, multiples of 3 (sum of digits tells you), 49, 77.
(This builds on @origimbo 's answer.)
answered Feb 29 '16 at 19:24
Ethan BolkerEthan Bolker
46k553120
$endgroup$
1
$begingroup$
Comparing this with @barak manos's approach, I would say that 119 and 133 also fall in the "look like a prime but aren't" category going up to 150. For me at least, 121 and 143 are "obviously" multiples of 11, but it probably depends on the person.
$endgroup$
– Mario Carneiro
Feb 29 '16 at 19:28
6
$begingroup$
For some reason I always think 51 looks prime and 41 doesn't. Don't know why. Still that's a pretty cute statement.
$endgroup$
– fleablood
Feb 29 '16 at 19:31
add a comment |
$begingroup$
Other answers cover things in far greater detail, but to expand on a comment by barak manos on their own answer, in terms of quick ways of testing and in order of speed of checking you can throw away:
- all even numbers
- all numbers whose digits end in five.
- all numbers whose digits add up to a multiple of three.
A couple of other small primes have more complicated tests, see for example here which covers 7 and 11.
answered Feb 29 '16 at 19:08
origimboorigimbo
1312
$endgroup$
2
$begingroup$
I'll never be able to remember the rule for division by 7 but "casting out" 7s is easy because 7 is a single digit. Given 840539438261 has the divisibility as 140539438261 which has the same as 539438261 as 119438261 as 49438261 as 438261 as 18261 as 4261 as 61 is not divisible by 7. You can do the same for any number but it's easiest for 7. It's the only way I know for 13. A number is divisible by 11 if the sum of the even place digits is the same as the odd placed digits or off by a multiple of 11.
$endgroup$
– fleablood
Feb 29 '16 at 19:41
$begingroup$
@fleablood: another test I learned for 7-divisibility is to subtract 21 times the least digit and then divide by 10. That is to say, discard the least digit and then subtract double the digit you discarded. Hence 840539438261 -> 84053943824 -> 8405394374 -> 840539429 -> 84053924 -> 8405384 -> 840530 > 84053 -> 8399 -> 821 -> 80 -> 8, so not divisible by 7. Note this doesn't tell you the modulus, whereas casting out does. You can do a similar trick for 17 using 51 in place of 21, and 13 using 39 (i.e. add 4 times the digit you chopped off).
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:49
$begingroup$
@SteveJessop don't understand. 840539438261 to 84053943824. Okay, that's just subtracting 21 and dividing by 10. 84053943824 to 8405394374. Okay the 2 is the least digit so we remove it. Then... the eight before the 2 becomes a 7????? why? Then 8405394374 to 840539429 ... so the 374 gets turned into 29? WTF?
$endgroup$
– fleablood
Mar 1 '16 at 17:04
$begingroup$
@fleablood: by "least digit" I mean "least significant digit", sorry. 84053943824, chop off the last digit would be 8405394382. The last digit was 4, so subtracting 8 from 8405394382 leaves 8405394374. The net result is that we have subtracted 21 * 4 and then divided by 10, both of which operations preserve divisibility by 7.
$endgroup$
– Steve Jessop
Mar 1 '16 at 17:07
$begingroup$
Hmmm... in my opinion multiplying and carrying is just as hard as doing a complete division. Casting out is faster and easier. Especially as we have 142 other numbers to test.
$endgroup$
– fleablood
Mar 1 '16 at 17:14
add a comment |
$begingroup$
I'd probably recommend just knowing all your primes between 7-150.
Start with 7 and count by 2s. If it looks prime, name it. The 3 exceptions between 1-100 are 57, 87 and 91. (I'm assuming "77" and "93" don't look prime to you.)
Keep counting past 100 and write your guesses down. Then check them all by Googling a list of prime numbers. Whichever ones you got wrong, memorize. This won't be many because you'll guess most right.
answered Mar 1 '16 at 14:54
djechlindjechlin
4,8401230
$endgroup$
add a comment |
$begingroup$
Prime numbers greater than 3 are of the form $6n pm 1$ , then you can test manually between 7 and 150. It will be easier than testing every odd integer as mentioned in other answer.
answered Mar 1 '16 at 15:08
Mojo JojoMojo Jojo
308112
$endgroup$
add a comment |
$begingroup$
There is no answer yet which points this out: A couple of years ago it was found that you can test for primality in polynomial time. See https://en.wikipedia.org/wiki/AKS_primality_test
answered Mar 1 '16 at 13:19
RobinRobin
1112
$endgroup$
$begingroup$
That's true, but given the OP is concerned with a 1-byte input, this breakthrough may not be terribly relevant :P
$endgroup$
– djechlin
Mar 1 '16 at 15:07
add a comment |
$begingroup$
Start with the square root of 150, the integer value is 12. Your prime divisors are 2 3 5 7 and 11. Eliminate the even numbers and the numbers ending in 5. The first test will be 3 squared or 9 in this case add 6 to 9 and so on to eliminate the 3s. The next test is 7 squared or 49 and this time add 14 to eliminate the 7s. The last test is 11 squared or 121 and this time add 22 to eliminate the 11s. The numbers left on your list should be prime numbers. Or Make a chart with 2, 3, 7, 9 on the left side and 0, 10, 20, 30 ..... 140 across the top. This eliminates the even numbers and numbers ending in 5. Then it's 3*3 = 9, 3*7 = 21, 3*9 = 27, 11*3 = 33 etc. Then 7*7 = 49, 7*11 = 77, 7*13 = 91 etc. Then 11*11 = 121
and 11*13 = 143 and the remaining numbers are prime.
answered Mar 2 '16 at 4:19
RayRay
393
$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%2f1676996%2ftests-for-prime-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
9 Answers
9
active
oldest
votes
9 Answers
9
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
That seems like a silly test question, but you can use the Sieve of Eratosthenes. Start with all numbers from 7 to 150 and start removing multiples of integers greater than 1. Animation from the Wikipedia link:
As for proving a number is prime, it is actually much easier to show that a number is not prime. Maybe you have some more idea of what you might see on a test, but those seem like irritating questions.
edited Feb 29 '16 at 16:36
Barry
2,093717
answered Feb 29 '16 at 12:33
CarserCarser
2,63541027
$endgroup$
12
$begingroup$
Note that you're done with the sieve when you reach the square root of the range, in this case $sqrt{150} approx~ 12$.
$endgroup$
– Daniel R. Collins
Feb 29 '16 at 14:15
$begingroup$
@RemcoGerlich He is correct (actually you want to test to $left lceil{sqrt{x}}right rceil $). See this question: stackoverflow.com/questions/5811151/…
$endgroup$
– Carser
Mar 1 '16 at 13:05
2
$begingroup$
@Jedediyah I assume you mean $lfloor sqrt{x} rfloor$.
$endgroup$
– Travis
Mar 1 '16 at 13:07
$begingroup$
@Travis Good assumption! ;p
$endgroup$
– Carser
Mar 1 '16 at 13:07
$begingroup$
@RemcoGerlich The animation actually does stop finding composite numbers at 11. You can see that after that test all of the remaining numbers are primes, and don't have any multiples that aren't already colored in.
$endgroup$
– Carser
Mar 1 '16 at 13:11
|
show 1 more comment
$begingroup$
That seems like a silly test question, but you can use the Sieve of Eratosthenes. Start with all numbers from 7 to 150 and start removing multiples of integers greater than 1. Animation from the Wikipedia link:
As for proving a number is prime, it is actually much easier to show that a number is not prime. Maybe you have some more idea of what you might see on a test, but those seem like irritating questions.
edited Feb 29 '16 at 16:36
Barry
2,093717
answered Feb 29 '16 at 12:33
CarserCarser
2,63541027
$endgroup$
12
$begingroup$
Note that you're done with the sieve when you reach the square root of the range, in this case $sqrt{150} approx~ 12$.
$endgroup$
– Daniel R. Collins
Feb 29 '16 at 14:15
$begingroup$
@RemcoGerlich He is correct (actually you want to test to $left lceil{sqrt{x}}right rceil $). See this question: stackoverflow.com/questions/5811151/…
$endgroup$
– Carser
Mar 1 '16 at 13:05
2
$begingroup$
@Jedediyah I assume you mean $lfloor sqrt{x} rfloor$.
$endgroup$
– Travis
Mar 1 '16 at 13:07
$begingroup$
@Travis Good assumption! ;p
$endgroup$
– Carser
Mar 1 '16 at 13:07
$begingroup$
@RemcoGerlich The animation actually does stop finding composite numbers at 11. You can see that after that test all of the remaining numbers are primes, and don't have any multiples that aren't already colored in.
$endgroup$
– Carser
Mar 1 '16 at 13:11
|
show 1 more comment
$begingroup$
That seems like a silly test question, but you can use the Sieve of Eratosthenes. Start with all numbers from 7 to 150 and start removing multiples of integers greater than 1. Animation from the Wikipedia link:
As for proving a number is prime, it is actually much easier to show that a number is not prime. Maybe you have some more idea of what you might see on a test, but those seem like irritating questions.
edited Feb 29 '16 at 16:36
Barry
2,093717
answered Feb 29 '16 at 12:33
CarserCarser
2,63541027
$endgroup$
That seems like a silly test question, but you can use the Sieve of Eratosthenes. Start with all numbers from 7 to 150 and start removing multiples of integers greater than 1. Animation from the Wikipedia link:
As for proving a number is prime, it is actually much easier to show that a number is not prime. Maybe you have some more idea of what you might see on a test, but those seem like irritating questions.
edited Feb 29 '16 at 16:36
Barry
2,093717
answered Feb 29 '16 at 12:33
CarserCarser
2,63541027
edited Feb 29 '16 at 16:36
Barry
2,093717
edited Feb 29 '16 at 16:36
Barry
2,093717
edited Feb 29 '16 at 16:36
Barry
2,093717
2,093717
answered Feb 29 '16 at 12:33
CarserCarser
2,63541027
answered Feb 29 '16 at 12:33
CarserCarser
2,63541027
answered Feb 29 '16 at 12:33
CarserCarser
2,63541027
2,63541027
12
$begingroup$
Note that you're done with the sieve when you reach the square root of the range, in this case $sqrt{150} approx~ 12$.
$endgroup$
– Daniel R. Collins
Feb 29 '16 at 14:15
$begingroup$
@RemcoGerlich He is correct (actually you want to test to $left lceil{sqrt{x}}right rceil $). See this question: stackoverflow.com/questions/5811151/…
$endgroup$
– Carser
Mar 1 '16 at 13:05
2
$begingroup$
@Jedediyah I assume you mean $lfloor sqrt{x} rfloor$.
$endgroup$
– Travis
Mar 1 '16 at 13:07
$begingroup$
@Travis Good assumption! ;p
$endgroup$
– Carser
Mar 1 '16 at 13:07
$begingroup$
@RemcoGerlich The animation actually does stop finding composite numbers at 11. You can see that after that test all of the remaining numbers are primes, and don't have any multiples that aren't already colored in.
$endgroup$
– Carser
Mar 1 '16 at 13:11
|
show 1 more comment
12
$begingroup$
Note that you're done with the sieve when you reach the square root of the range, in this case $sqrt{150} approx~ 12$.
$endgroup$
– Daniel R. Collins
Feb 29 '16 at 14:15
$begingroup$
@RemcoGerlich He is correct (actually you want to test to $left lceil{sqrt{x}}right rceil $). See this question: stackoverflow.com/questions/5811151/…
$endgroup$
– Carser
Mar 1 '16 at 13:05
2
$begingroup$
@Jedediyah I assume you mean $lfloor sqrt{x} rfloor$.
$endgroup$
– Travis
Mar 1 '16 at 13:07
$begingroup$
@Travis Good assumption! ;p
$endgroup$
– Carser
Mar 1 '16 at 13:07
$begingroup$
@RemcoGerlich The animation actually does stop finding composite numbers at 11. You can see that after that test all of the remaining numbers are primes, and don't have any multiples that aren't already colored in.
$endgroup$
– Carser
Mar 1 '16 at 13:11
12
12
$begingroup$
Note that you're done with the sieve when you reach the square root of the range, in this case $sqrt{150} approx~ 12$.
$endgroup$
– Daniel R. Collins
Feb 29 '16 at 14:15
$begingroup$
Note that you're done with the sieve when you reach the square root of the range, in this case $sqrt{150} approx~ 12$.
$endgroup$
– Daniel R. Collins
Feb 29 '16 at 14:15
$begingroup$
@RemcoGerlich He is correct (actually you want to test to $left lceil{sqrt{x}}right rceil $). See this question: stackoverflow.com/questions/5811151/…
$endgroup$
– Carser
Mar 1 '16 at 13:05
$begingroup$
@RemcoGerlich He is correct (actually you want to test to $left lceil{sqrt{x}}right rceil $). See this question: stackoverflow.com/questions/5811151/…
$endgroup$
– Carser
Mar 1 '16 at 13:05
2
2
$begingroup$
@Jedediyah I assume you mean $lfloor sqrt{x} rfloor$.
$endgroup$
– Travis
Mar 1 '16 at 13:07
$begingroup$
@Jedediyah I assume you mean $lfloor sqrt{x} rfloor$.
$endgroup$
– Travis
Mar 1 '16 at 13:07
$begingroup$
@Travis Good assumption! ;p
$endgroup$
– Carser
Mar 1 '16 at 13:07
$begingroup$
@Travis Good assumption! ;p
$endgroup$
– Carser
Mar 1 '16 at 13:07
$begingroup$
@RemcoGerlich The animation actually does stop finding composite numbers at 11. You can see that after that test all of the remaining numbers are primes, and don't have any multiples that aren't already colored in.
$endgroup$
– Carser
Mar 1 '16 at 13:11
$begingroup$
@RemcoGerlich The animation actually does stop finding composite numbers at 11. You can see that after that test all of the remaining numbers are primes, and don't have any multiples that aren't already colored in.
$endgroup$
– Carser
Mar 1 '16 at 13:11
|
show 1 more comment
$begingroup$
The illustrated answer above is cool.
Here is something that might be quicker for you during an exam.
The prime numbers between $7$ and $150$ are all the neighbors of multiples of $6$, except:
- Those that end with $5$
- $49$
- $77$
- $91$
- $119$
- $121$
- $133$
- $143$
So you can simply:
- List all multiples of $6$
- List the two neighbors next to each one of them
- Memorize the ones mentioned above and eliminate them
UPDATE:
Just in order to clarify (and simplify) the method mentioned above.
All you have to do is to write down two lists, one starting from $7$ and the other starting from $11$.
Increment each list by $6$ until $150$, and eliminate the values that you have memorized in advance.
$require{cancel}$
- $small7,13,19,colorred{cancel{25}},31,37,43,colorgreen{cancel{49}},colorred{cancel{55}},61,67,73,79,colorred{cancel{85}},colorgreen{cancel{91}},97,103,109,colorred{cancel{115}},colorgreen{cancel{121}},127,colorgreen{cancel{133}},139,colorred{cancel{145}}$
- $small11,17,23,29,colorred{cancel{35}},41,47,53,59,colorred{cancel{65}},71,colorgreen{cancel{77}},83,89,colorred{cancel{95}},101,107,113,colorgreen{cancel{119}},colorred{cancel{125}},131,137,colorgreen{cancel{143}},149$
answered Feb 29 '16 at 12:43
barak manosbarak manos
38k742103
$endgroup$
5
$begingroup$
Yeah I definitely agree that if you know the range of numbers then it is easier to just memorize the primes in that interval.
$endgroup$
– Carser
Feb 29 '16 at 12:47
$begingroup$
@Jedediyah: Assuming that the range is small of course.
$endgroup$
– barak manos
Feb 29 '16 at 12:48
$begingroup$
@Jedediyah: And in the case above, you can just as well check the divisibility of each number in that range by $2,3,5,7,11$ (out of which, the first three are rather easy).
$endgroup$
– barak manos
Feb 29 '16 at 12:49
1
$begingroup$
For the range, doing the one away from a multiple of six you only need to check divisibility by 5,7,11 Five is obvious 11 almost obvious (there are only 13 of them and the single digit ones are obvious. With these tricks it shouldn't take more than a minute even with being very careful.
$endgroup$
– fleablood
Feb 29 '16 at 16:55
3
$begingroup$
@fleablood: 143 doesn't have smaller factors than 11 :-) I think the problem here is more or less what the questioner suggests in the question: rushing it under stress will cause mistakes, taking it slowly and methodically might take too long. As barak shows it's possible to prepare specifically to list primes up to 150 quickly (heck, you could just memorise the sequence of primes). But if you do that and then you're actually asked to list primes up to 160 quickly then your short-cuts may or may not still be valid.
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:36
|
show 6 more comments
$begingroup$
The illustrated answer above is cool.
Here is something that might be quicker for you during an exam.
The prime numbers between $7$ and $150$ are all the neighbors of multiples of $6$, except:
- Those that end with $5$
- $49$
- $77$
- $91$
- $119$
- $121$
- $133$
- $143$
So you can simply:
- List all multiples of $6$
- List the two neighbors next to each one of them
- Memorize the ones mentioned above and eliminate them
UPDATE:
Just in order to clarify (and simplify) the method mentioned above.
All you have to do is to write down two lists, one starting from $7$ and the other starting from $11$.
Increment each list by $6$ until $150$, and eliminate the values that you have memorized in advance.
$require{cancel}$
- $small7,13,19,colorred{cancel{25}},31,37,43,colorgreen{cancel{49}},colorred{cancel{55}},61,67,73,79,colorred{cancel{85}},colorgreen{cancel{91}},97,103,109,colorred{cancel{115}},colorgreen{cancel{121}},127,colorgreen{cancel{133}},139,colorred{cancel{145}}$
- $small11,17,23,29,colorred{cancel{35}},41,47,53,59,colorred{cancel{65}},71,colorgreen{cancel{77}},83,89,colorred{cancel{95}},101,107,113,colorgreen{cancel{119}},colorred{cancel{125}},131,137,colorgreen{cancel{143}},149$
answered Feb 29 '16 at 12:43
barak manosbarak manos
38k742103
$endgroup$
5
$begingroup$
Yeah I definitely agree that if you know the range of numbers then it is easier to just memorize the primes in that interval.
$endgroup$
– Carser
Feb 29 '16 at 12:47
$begingroup$
@Jedediyah: Assuming that the range is small of course.
$endgroup$
– barak manos
Feb 29 '16 at 12:48
$begingroup$
@Jedediyah: And in the case above, you can just as well check the divisibility of each number in that range by $2,3,5,7,11$ (out of which, the first three are rather easy).
$endgroup$
– barak manos
Feb 29 '16 at 12:49
1
$begingroup$
For the range, doing the one away from a multiple of six you only need to check divisibility by 5,7,11 Five is obvious 11 almost obvious (there are only 13 of them and the single digit ones are obvious. With these tricks it shouldn't take more than a minute even with being very careful.
$endgroup$
– fleablood
Feb 29 '16 at 16:55
3
$begingroup$
@fleablood: 143 doesn't have smaller factors than 11 :-) I think the problem here is more or less what the questioner suggests in the question: rushing it under stress will cause mistakes, taking it slowly and methodically might take too long. As barak shows it's possible to prepare specifically to list primes up to 150 quickly (heck, you could just memorise the sequence of primes). But if you do that and then you're actually asked to list primes up to 160 quickly then your short-cuts may or may not still be valid.
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:36
|
show 6 more comments
$begingroup$
The illustrated answer above is cool.
Here is something that might be quicker for you during an exam.
The prime numbers between $7$ and $150$ are all the neighbors of multiples of $6$, except:
- Those that end with $5$
- $49$
- $77$
- $91$
- $119$
- $121$
- $133$
- $143$
So you can simply:
- List all multiples of $6$
- List the two neighbors next to each one of them
- Memorize the ones mentioned above and eliminate them
UPDATE:
Just in order to clarify (and simplify) the method mentioned above.
All you have to do is to write down two lists, one starting from $7$ and the other starting from $11$.
Increment each list by $6$ until $150$, and eliminate the values that you have memorized in advance.
$require{cancel}$
- $small7,13,19,colorred{cancel{25}},31,37,43,colorgreen{cancel{49}},colorred{cancel{55}},61,67,73,79,colorred{cancel{85}},colorgreen{cancel{91}},97,103,109,colorred{cancel{115}},colorgreen{cancel{121}},127,colorgreen{cancel{133}},139,colorred{cancel{145}}$
- $small11,17,23,29,colorred{cancel{35}},41,47,53,59,colorred{cancel{65}},71,colorgreen{cancel{77}},83,89,colorred{cancel{95}},101,107,113,colorgreen{cancel{119}},colorred{cancel{125}},131,137,colorgreen{cancel{143}},149$
answered Feb 29 '16 at 12:43
barak manosbarak manos
38k742103
$endgroup$
The illustrated answer above is cool.
Here is something that might be quicker for you during an exam.
The prime numbers between $7$ and $150$ are all the neighbors of multiples of $6$, except:
- Those that end with $5$
- $49$
- $77$
- $91$
- $119$
- $121$
- $133$
- $143$
So you can simply:
- List all multiples of $6$
- List the two neighbors next to each one of them
- Memorize the ones mentioned above and eliminate them
UPDATE:
Just in order to clarify (and simplify) the method mentioned above.
All you have to do is to write down two lists, one starting from $7$ and the other starting from $11$.
Increment each list by $6$ until $150$, and eliminate the values that you have memorized in advance.
$require{cancel}$
- $small7,13,19,colorred{cancel{25}},31,37,43,colorgreen{cancel{49}},colorred{cancel{55}},61,67,73,79,colorred{cancel{85}},colorgreen{cancel{91}},97,103,109,colorred{cancel{115}},colorgreen{cancel{121}},127,colorgreen{cancel{133}},139,colorred{cancel{145}}$
- $small11,17,23,29,colorred{cancel{35}},41,47,53,59,colorred{cancel{65}},71,colorgreen{cancel{77}},83,89,colorred{cancel{95}},101,107,113,colorgreen{cancel{119}},colorred{cancel{125}},131,137,colorgreen{cancel{143}},149$
answered Feb 29 '16 at 12:43
barak manosbarak manos
38k742103
edited Mar 1 '16 at 15:07
answered Feb 29 '16 at 12:43
barak manosbarak manos
38k742103
answered Feb 29 '16 at 12:43
barak manosbarak manos
38k742103
answered Feb 29 '16 at 12:43
barak manosbarak manos
38k742103
38k742103
5
$begingroup$
Yeah I definitely agree that if you know the range of numbers then it is easier to just memorize the primes in that interval.
$endgroup$
– Carser
Feb 29 '16 at 12:47
$begingroup$
@Jedediyah: Assuming that the range is small of course.
$endgroup$
– barak manos
Feb 29 '16 at 12:48
$begingroup$
@Jedediyah: And in the case above, you can just as well check the divisibility of each number in that range by $2,3,5,7,11$ (out of which, the first three are rather easy).
$endgroup$
– barak manos
Feb 29 '16 at 12:49
1
$begingroup$
For the range, doing the one away from a multiple of six you only need to check divisibility by 5,7,11 Five is obvious 11 almost obvious (there are only 13 of them and the single digit ones are obvious. With these tricks it shouldn't take more than a minute even with being very careful.
$endgroup$
– fleablood
Feb 29 '16 at 16:55
3
$begingroup$
@fleablood: 143 doesn't have smaller factors than 11 :-) I think the problem here is more or less what the questioner suggests in the question: rushing it under stress will cause mistakes, taking it slowly and methodically might take too long. As barak shows it's possible to prepare specifically to list primes up to 150 quickly (heck, you could just memorise the sequence of primes). But if you do that and then you're actually asked to list primes up to 160 quickly then your short-cuts may or may not still be valid.
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:36
|
show 6 more comments
5
$begingroup$
Yeah I definitely agree that if you know the range of numbers then it is easier to just memorize the primes in that interval.
$endgroup$
– Carser
Feb 29 '16 at 12:47
$begingroup$
@Jedediyah: Assuming that the range is small of course.
$endgroup$
– barak manos
Feb 29 '16 at 12:48
$begingroup$
@Jedediyah: And in the case above, you can just as well check the divisibility of each number in that range by $2,3,5,7,11$ (out of which, the first three are rather easy).
$endgroup$
– barak manos
Feb 29 '16 at 12:49
1
$begingroup$
For the range, doing the one away from a multiple of six you only need to check divisibility by 5,7,11 Five is obvious 11 almost obvious (there are only 13 of them and the single digit ones are obvious. With these tricks it shouldn't take more than a minute even with being very careful.
$endgroup$
– fleablood
Feb 29 '16 at 16:55
3
$begingroup$
@fleablood: 143 doesn't have smaller factors than 11 :-) I think the problem here is more or less what the questioner suggests in the question: rushing it under stress will cause mistakes, taking it slowly and methodically might take too long. As barak shows it's possible to prepare specifically to list primes up to 150 quickly (heck, you could just memorise the sequence of primes). But if you do that and then you're actually asked to list primes up to 160 quickly then your short-cuts may or may not still be valid.
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:36
5
5
$begingroup$
Yeah I definitely agree that if you know the range of numbers then it is easier to just memorize the primes in that interval.
$endgroup$
– Carser
Feb 29 '16 at 12:47
$begingroup$
Yeah I definitely agree that if you know the range of numbers then it is easier to just memorize the primes in that interval.
$endgroup$
– Carser
Feb 29 '16 at 12:47
$begingroup$
@Jedediyah: Assuming that the range is small of course.
$endgroup$
– barak manos
Feb 29 '16 at 12:48
$begingroup$
@Jedediyah: Assuming that the range is small of course.
$endgroup$
– barak manos
Feb 29 '16 at 12:48
$begingroup$
@Jedediyah: And in the case above, you can just as well check the divisibility of each number in that range by $2,3,5,7,11$ (out of which, the first three are rather easy).
$endgroup$
– barak manos
Feb 29 '16 at 12:49
$begingroup$
@Jedediyah: And in the case above, you can just as well check the divisibility of each number in that range by $2,3,5,7,11$ (out of which, the first three are rather easy).
$endgroup$
– barak manos
Feb 29 '16 at 12:49
1
1
$begingroup$
For the range, doing the one away from a multiple of six you only need to check divisibility by 5,7,11 Five is obvious 11 almost obvious (there are only 13 of them and the single digit ones are obvious. With these tricks it shouldn't take more than a minute even with being very careful.
$endgroup$
– fleablood
Feb 29 '16 at 16:55
$begingroup$
For the range, doing the one away from a multiple of six you only need to check divisibility by 5,7,11 Five is obvious 11 almost obvious (there are only 13 of them and the single digit ones are obvious. With these tricks it shouldn't take more than a minute even with being very careful.
$endgroup$
– fleablood
Feb 29 '16 at 16:55
3
3
$begingroup$
@fleablood: 143 doesn't have smaller factors than 11 :-) I think the problem here is more or less what the questioner suggests in the question: rushing it under stress will cause mistakes, taking it slowly and methodically might take too long. As barak shows it's possible to prepare specifically to list primes up to 150 quickly (heck, you could just memorise the sequence of primes). But if you do that and then you're actually asked to list primes up to 160 quickly then your short-cuts may or may not still be valid.
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:36
$begingroup$
@fleablood: 143 doesn't have smaller factors than 11 :-) I think the problem here is more or less what the questioner suggests in the question: rushing it under stress will cause mistakes, taking it slowly and methodically might take too long. As barak shows it's possible to prepare specifically to list primes up to 150 quickly (heck, you could just memorise the sequence of primes). But if you do that and then you're actually asked to list primes up to 160 quickly then your short-cuts may or may not still be valid.
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:36
|
show 6 more comments
$begingroup$
Given a number $n$.
You need to (1) find all primes smaller than $sqrt{n}$ and (2) see if any of them divides $n$.
If none of them divides $n$ then you have a prime, otherwise it's a composite number.
Example:
Is 147 prime?
$sqrt{147} < 13$ so we have 2, 3, 5, 7, and 11 to check.
3 divides 147 so we don't need to look further.
147 is a composite number.
answered Feb 29 '16 at 14:33
snoramsnoram
454313
$endgroup$
1
$begingroup$
The fact we are building on is that if $n$ is a composite then it has a prime factor smaller than $sqrt{n}$. The proof is easy.
$endgroup$
– snoram
Feb 29 '16 at 14:35
4
$begingroup$
The would take an incredibly long time if you need to do it on every number between 7 and 150 and the OP already knows how to do that. S/he specifically asked for a method to avoid having to check every single number.
$endgroup$
– fleablood
Feb 29 '16 at 16:50
$begingroup$
Agreed it would take long time. But disagree that the question is clear on exactly what is being asked. It ends with two questions "Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ? "
$endgroup$
– snoram
Mar 1 '16 at 7:10
$begingroup$
My answer addresses both questions.
$endgroup$
– snoram
Mar 1 '16 at 9:27
add a comment |
$begingroup$
Given a number $n$.
You need to (1) find all primes smaller than $sqrt{n}$ and (2) see if any of them divides $n$.
If none of them divides $n$ then you have a prime, otherwise it's a composite number.
Example:
Is 147 prime?
$sqrt{147} < 13$ so we have 2, 3, 5, 7, and 11 to check.
3 divides 147 so we don't need to look further.
147 is a composite number.
answered Feb 29 '16 at 14:33
snoramsnoram
454313
$endgroup$
1
$begingroup$
The fact we are building on is that if $n$ is a composite then it has a prime factor smaller than $sqrt{n}$. The proof is easy.
$endgroup$
– snoram
Feb 29 '16 at 14:35
4
$begingroup$
The would take an incredibly long time if you need to do it on every number between 7 and 150 and the OP already knows how to do that. S/he specifically asked for a method to avoid having to check every single number.
$endgroup$
– fleablood
Feb 29 '16 at 16:50
$begingroup$
Agreed it would take long time. But disagree that the question is clear on exactly what is being asked. It ends with two questions "Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ? "
$endgroup$
– snoram
Mar 1 '16 at 7:10
$begingroup$
My answer addresses both questions.
$endgroup$
– snoram
Mar 1 '16 at 9:27
add a comment |
$begingroup$
Given a number $n$.
You need to (1) find all primes smaller than $sqrt{n}$ and (2) see if any of them divides $n$.
If none of them divides $n$ then you have a prime, otherwise it's a composite number.
Example:
Is 147 prime?
$sqrt{147} < 13$ so we have 2, 3, 5, 7, and 11 to check.
3 divides 147 so we don't need to look further.
147 is a composite number.
answered Feb 29 '16 at 14:33
snoramsnoram
454313
$endgroup$
Given a number $n$.
You need to (1) find all primes smaller than $sqrt{n}$ and (2) see if any of them divides $n$.
If none of them divides $n$ then you have a prime, otherwise it's a composite number.
Example:
Is 147 prime?
$sqrt{147} < 13$ so we have 2, 3, 5, 7, and 11 to check.
3 divides 147 so we don't need to look further.
147 is a composite number.
answered Feb 29 '16 at 14:33
snoramsnoram
454313
edited Feb 29 '16 at 15:04
answered Feb 29 '16 at 14:33
snoramsnoram
454313
answered Feb 29 '16 at 14:33
snoramsnoram
454313
answered Feb 29 '16 at 14:33
snoramsnoram
454313
454313
1
$begingroup$
The fact we are building on is that if $n$ is a composite then it has a prime factor smaller than $sqrt{n}$. The proof is easy.
$endgroup$
– snoram
Feb 29 '16 at 14:35
4
$begingroup$
The would take an incredibly long time if you need to do it on every number between 7 and 150 and the OP already knows how to do that. S/he specifically asked for a method to avoid having to check every single number.
$endgroup$
– fleablood
Feb 29 '16 at 16:50
$begingroup$
Agreed it would take long time. But disagree that the question is clear on exactly what is being asked. It ends with two questions "Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ? "
$endgroup$
– snoram
Mar 1 '16 at 7:10
$begingroup$
My answer addresses both questions.
$endgroup$
– snoram
Mar 1 '16 at 9:27
add a comment |
1
$begingroup$
The fact we are building on is that if $n$ is a composite then it has a prime factor smaller than $sqrt{n}$. The proof is easy.
$endgroup$
– snoram
Feb 29 '16 at 14:35
4
$begingroup$
The would take an incredibly long time if you need to do it on every number between 7 and 150 and the OP already knows how to do that. S/he specifically asked for a method to avoid having to check every single number.
$endgroup$
– fleablood
Feb 29 '16 at 16:50
$begingroup$
Agreed it would take long time. But disagree that the question is clear on exactly what is being asked. It ends with two questions "Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ? "
$endgroup$
– snoram
Mar 1 '16 at 7:10
$begingroup$
My answer addresses both questions.
$endgroup$
– snoram
Mar 1 '16 at 9:27
1
1
$begingroup$
The fact we are building on is that if $n$ is a composite then it has a prime factor smaller than $sqrt{n}$. The proof is easy.
$endgroup$
– snoram
Feb 29 '16 at 14:35
$begingroup$
The fact we are building on is that if $n$ is a composite then it has a prime factor smaller than $sqrt{n}$. The proof is easy.
$endgroup$
– snoram
Feb 29 '16 at 14:35
4
4
$begingroup$
The would take an incredibly long time if you need to do it on every number between 7 and 150 and the OP already knows how to do that. S/he specifically asked for a method to avoid having to check every single number.
$endgroup$
– fleablood
Feb 29 '16 at 16:50
$begingroup$
The would take an incredibly long time if you need to do it on every number between 7 and 150 and the OP already knows how to do that. S/he specifically asked for a method to avoid having to check every single number.
$endgroup$
– fleablood
Feb 29 '16 at 16:50
$begingroup$
Agreed it would take long time. But disagree that the question is clear on exactly what is being asked. It ends with two questions "Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ? "
$endgroup$
– snoram
Mar 1 '16 at 7:10
$begingroup$
Agreed it would take long time. But disagree that the question is clear on exactly what is being asked. It ends with two questions "Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ? "
$endgroup$
– snoram
Mar 1 '16 at 7:10
$begingroup$
My answer addresses both questions.
$endgroup$
– snoram
Mar 1 '16 at 9:27
$begingroup$
My answer addresses both questions.
$endgroup$
– snoram
Mar 1 '16 at 9:27
add a comment |
$begingroup$
My favorite mnemonic:
91 is the only number less than 100 that looks like a prime and isn't.
That's because these numbers don't look like primes: evens, multiples of 5, multiples of 3 (sum of digits tells you), 49, 77.
(This builds on @origimbo 's answer.)
answered Feb 29 '16 at 19:24
Ethan BolkerEthan Bolker
46k553120
$endgroup$
1
$begingroup$
Comparing this with @barak manos's approach, I would say that 119 and 133 also fall in the "look like a prime but aren't" category going up to 150. For me at least, 121 and 143 are "obviously" multiples of 11, but it probably depends on the person.
$endgroup$
– Mario Carneiro
Feb 29 '16 at 19:28
6
$begingroup$
For some reason I always think 51 looks prime and 41 doesn't. Don't know why. Still that's a pretty cute statement.
$endgroup$
– fleablood
Feb 29 '16 at 19:31
add a comment |
$begingroup$
My favorite mnemonic:
91 is the only number less than 100 that looks like a prime and isn't.
That's because these numbers don't look like primes: evens, multiples of 5, multiples of 3 (sum of digits tells you), 49, 77.
(This builds on @origimbo 's answer.)
answered Feb 29 '16 at 19:24
Ethan BolkerEthan Bolker
46k553120
$endgroup$
1
$begingroup$
Comparing this with @barak manos's approach, I would say that 119 and 133 also fall in the "look like a prime but aren't" category going up to 150. For me at least, 121 and 143 are "obviously" multiples of 11, but it probably depends on the person.
$endgroup$
– Mario Carneiro
Feb 29 '16 at 19:28
6
$begingroup$
For some reason I always think 51 looks prime and 41 doesn't. Don't know why. Still that's a pretty cute statement.
$endgroup$
– fleablood
Feb 29 '16 at 19:31
add a comment |
$begingroup$
My favorite mnemonic:
91 is the only number less than 100 that looks like a prime and isn't.
That's because these numbers don't look like primes: evens, multiples of 5, multiples of 3 (sum of digits tells you), 49, 77.
(This builds on @origimbo 's answer.)
answered Feb 29 '16 at 19:24
Ethan BolkerEthan Bolker
46k553120
$endgroup$
My favorite mnemonic:
91 is the only number less than 100 that looks like a prime and isn't.
That's because these numbers don't look like primes: evens, multiples of 5, multiples of 3 (sum of digits tells you), 49, 77.
(This builds on @origimbo 's answer.)
answered Feb 29 '16 at 19:24
Ethan BolkerEthan Bolker
46k553120
answered Feb 29 '16 at 19:24
Ethan BolkerEthan Bolker
46k553120
answered Feb 29 '16 at 19:24
Ethan BolkerEthan Bolker
46k553120
answered Feb 29 '16 at 19:24
Ethan BolkerEthan Bolker
46k553120
46k553120
1
$begingroup$
Comparing this with @barak manos's approach, I would say that 119 and 133 also fall in the "look like a prime but aren't" category going up to 150. For me at least, 121 and 143 are "obviously" multiples of 11, but it probably depends on the person.
$endgroup$
– Mario Carneiro
Feb 29 '16 at 19:28
6
$begingroup$
For some reason I always think 51 looks prime and 41 doesn't. Don't know why. Still that's a pretty cute statement.
$endgroup$
– fleablood
Feb 29 '16 at 19:31
add a comment |
1
$begingroup$
Comparing this with @barak manos's approach, I would say that 119 and 133 also fall in the "look like a prime but aren't" category going up to 150. For me at least, 121 and 143 are "obviously" multiples of 11, but it probably depends on the person.
$endgroup$
– Mario Carneiro
Feb 29 '16 at 19:28
6
$begingroup$
For some reason I always think 51 looks prime and 41 doesn't. Don't know why. Still that's a pretty cute statement.
$endgroup$
– fleablood
Feb 29 '16 at 19:31
1
1
$begingroup$
Comparing this with @barak manos's approach, I would say that 119 and 133 also fall in the "look like a prime but aren't" category going up to 150. For me at least, 121 and 143 are "obviously" multiples of 11, but it probably depends on the person.
$endgroup$
– Mario Carneiro
Feb 29 '16 at 19:28
$begingroup$
Comparing this with @barak manos's approach, I would say that 119 and 133 also fall in the "look like a prime but aren't" category going up to 150. For me at least, 121 and 143 are "obviously" multiples of 11, but it probably depends on the person.
$endgroup$
– Mario Carneiro
Feb 29 '16 at 19:28
6
6
$begingroup$
For some reason I always think 51 looks prime and 41 doesn't. Don't know why. Still that's a pretty cute statement.
$endgroup$
– fleablood
Feb 29 '16 at 19:31
$begingroup$
For some reason I always think 51 looks prime and 41 doesn't. Don't know why. Still that's a pretty cute statement.
$endgroup$
– fleablood
Feb 29 '16 at 19:31
add a comment |
$begingroup$
Other answers cover things in far greater detail, but to expand on a comment by barak manos on their own answer, in terms of quick ways of testing and in order of speed of checking you can throw away:
- all even numbers
- all numbers whose digits end in five.
- all numbers whose digits add up to a multiple of three.
A couple of other small primes have more complicated tests, see for example here which covers 7 and 11.
answered Feb 29 '16 at 19:08
origimboorigimbo
1312
$endgroup$
2
$begingroup$
I'll never be able to remember the rule for division by 7 but "casting out" 7s is easy because 7 is a single digit. Given 840539438261 has the divisibility as 140539438261 which has the same as 539438261 as 119438261 as 49438261 as 438261 as 18261 as 4261 as 61 is not divisible by 7. You can do the same for any number but it's easiest for 7. It's the only way I know for 13. A number is divisible by 11 if the sum of the even place digits is the same as the odd placed digits or off by a multiple of 11.
$endgroup$
– fleablood
Feb 29 '16 at 19:41
$begingroup$
@fleablood: another test I learned for 7-divisibility is to subtract 21 times the least digit and then divide by 10. That is to say, discard the least digit and then subtract double the digit you discarded. Hence 840539438261 -> 84053943824 -> 8405394374 -> 840539429 -> 84053924 -> 8405384 -> 840530 > 84053 -> 8399 -> 821 -> 80 -> 8, so not divisible by 7. Note this doesn't tell you the modulus, whereas casting out does. You can do a similar trick for 17 using 51 in place of 21, and 13 using 39 (i.e. add 4 times the digit you chopped off).
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:49
$begingroup$
@SteveJessop don't understand. 840539438261 to 84053943824. Okay, that's just subtracting 21 and dividing by 10. 84053943824 to 8405394374. Okay the 2 is the least digit so we remove it. Then... the eight before the 2 becomes a 7????? why? Then 8405394374 to 840539429 ... so the 374 gets turned into 29? WTF?
$endgroup$
– fleablood
Mar 1 '16 at 17:04
$begingroup$
@fleablood: by "least digit" I mean "least significant digit", sorry. 84053943824, chop off the last digit would be 8405394382. The last digit was 4, so subtracting 8 from 8405394382 leaves 8405394374. The net result is that we have subtracted 21 * 4 and then divided by 10, both of which operations preserve divisibility by 7.
$endgroup$
– Steve Jessop
Mar 1 '16 at 17:07
$begingroup$
Hmmm... in my opinion multiplying and carrying is just as hard as doing a complete division. Casting out is faster and easier. Especially as we have 142 other numbers to test.
$endgroup$
– fleablood
Mar 1 '16 at 17:14
add a comment |
$begingroup$
Other answers cover things in far greater detail, but to expand on a comment by barak manos on their own answer, in terms of quick ways of testing and in order of speed of checking you can throw away:
- all even numbers
- all numbers whose digits end in five.
- all numbers whose digits add up to a multiple of three.
A couple of other small primes have more complicated tests, see for example here which covers 7 and 11.
answered Feb 29 '16 at 19:08
origimboorigimbo
1312
$endgroup$
2
$begingroup$
I'll never be able to remember the rule for division by 7 but "casting out" 7s is easy because 7 is a single digit. Given 840539438261 has the divisibility as 140539438261 which has the same as 539438261 as 119438261 as 49438261 as 438261 as 18261 as 4261 as 61 is not divisible by 7. You can do the same for any number but it's easiest for 7. It's the only way I know for 13. A number is divisible by 11 if the sum of the even place digits is the same as the odd placed digits or off by a multiple of 11.
$endgroup$
– fleablood
Feb 29 '16 at 19:41
$begingroup$
@fleablood: another test I learned for 7-divisibility is to subtract 21 times the least digit and then divide by 10. That is to say, discard the least digit and then subtract double the digit you discarded. Hence 840539438261 -> 84053943824 -> 8405394374 -> 840539429 -> 84053924 -> 8405384 -> 840530 > 84053 -> 8399 -> 821 -> 80 -> 8, so not divisible by 7. Note this doesn't tell you the modulus, whereas casting out does. You can do a similar trick for 17 using 51 in place of 21, and 13 using 39 (i.e. add 4 times the digit you chopped off).
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:49
$begingroup$
@SteveJessop don't understand. 840539438261 to 84053943824. Okay, that's just subtracting 21 and dividing by 10. 84053943824 to 8405394374. Okay the 2 is the least digit so we remove it. Then... the eight before the 2 becomes a 7????? why? Then 8405394374 to 840539429 ... so the 374 gets turned into 29? WTF?
$endgroup$
– fleablood
Mar 1 '16 at 17:04
$begingroup$
@fleablood: by "least digit" I mean "least significant digit", sorry. 84053943824, chop off the last digit would be 8405394382. The last digit was 4, so subtracting 8 from 8405394382 leaves 8405394374. The net result is that we have subtracted 21 * 4 and then divided by 10, both of which operations preserve divisibility by 7.
$endgroup$
– Steve Jessop
Mar 1 '16 at 17:07
$begingroup$
Hmmm... in my opinion multiplying and carrying is just as hard as doing a complete division. Casting out is faster and easier. Especially as we have 142 other numbers to test.
$endgroup$
– fleablood
Mar 1 '16 at 17:14
add a comment |
$begingroup$
Other answers cover things in far greater detail, but to expand on a comment by barak manos on their own answer, in terms of quick ways of testing and in order of speed of checking you can throw away:
- all even numbers
- all numbers whose digits end in five.
- all numbers whose digits add up to a multiple of three.
A couple of other small primes have more complicated tests, see for example here which covers 7 and 11.
answered Feb 29 '16 at 19:08
origimboorigimbo
1312
$endgroup$
Other answers cover things in far greater detail, but to expand on a comment by barak manos on their own answer, in terms of quick ways of testing and in order of speed of checking you can throw away:
- all even numbers
- all numbers whose digits end in five.
- all numbers whose digits add up to a multiple of three.
A couple of other small primes have more complicated tests, see for example here which covers 7 and 11.
answered Feb 29 '16 at 19:08
origimboorigimbo
1312
answered Feb 29 '16 at 19:08
origimboorigimbo
1312
answered Feb 29 '16 at 19:08
origimboorigimbo
1312
answered Feb 29 '16 at 19:08
origimboorigimbo
1312
1312
2
$begingroup$
I'll never be able to remember the rule for division by 7 but "casting out" 7s is easy because 7 is a single digit. Given 840539438261 has the divisibility as 140539438261 which has the same as 539438261 as 119438261 as 49438261 as 438261 as 18261 as 4261 as 61 is not divisible by 7. You can do the same for any number but it's easiest for 7. It's the only way I know for 13. A number is divisible by 11 if the sum of the even place digits is the same as the odd placed digits or off by a multiple of 11.
$endgroup$
– fleablood
Feb 29 '16 at 19:41
$begingroup$
@fleablood: another test I learned for 7-divisibility is to subtract 21 times the least digit and then divide by 10. That is to say, discard the least digit and then subtract double the digit you discarded. Hence 840539438261 -> 84053943824 -> 8405394374 -> 840539429 -> 84053924 -> 8405384 -> 840530 > 84053 -> 8399 -> 821 -> 80 -> 8, so not divisible by 7. Note this doesn't tell you the modulus, whereas casting out does. You can do a similar trick for 17 using 51 in place of 21, and 13 using 39 (i.e. add 4 times the digit you chopped off).
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:49
$begingroup$
@SteveJessop don't understand. 840539438261 to 84053943824. Okay, that's just subtracting 21 and dividing by 10. 84053943824 to 8405394374. Okay the 2 is the least digit so we remove it. Then... the eight before the 2 becomes a 7????? why? Then 8405394374 to 840539429 ... so the 374 gets turned into 29? WTF?
$endgroup$
– fleablood
Mar 1 '16 at 17:04
$begingroup$
@fleablood: by "least digit" I mean "least significant digit", sorry. 84053943824, chop off the last digit would be 8405394382. The last digit was 4, so subtracting 8 from 8405394382 leaves 8405394374. The net result is that we have subtracted 21 * 4 and then divided by 10, both of which operations preserve divisibility by 7.
$endgroup$
– Steve Jessop
Mar 1 '16 at 17:07
$begingroup$
Hmmm... in my opinion multiplying and carrying is just as hard as doing a complete division. Casting out is faster and easier. Especially as we have 142 other numbers to test.
$endgroup$
– fleablood
Mar 1 '16 at 17:14
add a comment |
2
$begingroup$
I'll never be able to remember the rule for division by 7 but "casting out" 7s is easy because 7 is a single digit. Given 840539438261 has the divisibility as 140539438261 which has the same as 539438261 as 119438261 as 49438261 as 438261 as 18261 as 4261 as 61 is not divisible by 7. You can do the same for any number but it's easiest for 7. It's the only way I know for 13. A number is divisible by 11 if the sum of the even place digits is the same as the odd placed digits or off by a multiple of 11.
$endgroup$
– fleablood
Feb 29 '16 at 19:41
$begingroup$
@fleablood: another test I learned for 7-divisibility is to subtract 21 times the least digit and then divide by 10. That is to say, discard the least digit and then subtract double the digit you discarded. Hence 840539438261 -> 84053943824 -> 8405394374 -> 840539429 -> 84053924 -> 8405384 -> 840530 > 84053 -> 8399 -> 821 -> 80 -> 8, so not divisible by 7. Note this doesn't tell you the modulus, whereas casting out does. You can do a similar trick for 17 using 51 in place of 21, and 13 using 39 (i.e. add 4 times the digit you chopped off).
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:49
$begingroup$
@SteveJessop don't understand. 840539438261 to 84053943824. Okay, that's just subtracting 21 and dividing by 10. 84053943824 to 8405394374. Okay the 2 is the least digit so we remove it. Then... the eight before the 2 becomes a 7????? why? Then 8405394374 to 840539429 ... so the 374 gets turned into 29? WTF?
$endgroup$
– fleablood
Mar 1 '16 at 17:04
$begingroup$
@fleablood: by "least digit" I mean "least significant digit", sorry. 84053943824, chop off the last digit would be 8405394382. The last digit was 4, so subtracting 8 from 8405394382 leaves 8405394374. The net result is that we have subtracted 21 * 4 and then divided by 10, both of which operations preserve divisibility by 7.
$endgroup$
– Steve Jessop
Mar 1 '16 at 17:07
$begingroup$
Hmmm... in my opinion multiplying and carrying is just as hard as doing a complete division. Casting out is faster and easier. Especially as we have 142 other numbers to test.
$endgroup$
– fleablood
Mar 1 '16 at 17:14
2
2
$begingroup$
I'll never be able to remember the rule for division by 7 but "casting out" 7s is easy because 7 is a single digit. Given 840539438261 has the divisibility as 140539438261 which has the same as 539438261 as 119438261 as 49438261 as 438261 as 18261 as 4261 as 61 is not divisible by 7. You can do the same for any number but it's easiest for 7. It's the only way I know for 13. A number is divisible by 11 if the sum of the even place digits is the same as the odd placed digits or off by a multiple of 11.
$endgroup$
– fleablood
Feb 29 '16 at 19:41
$begingroup$
I'll never be able to remember the rule for division by 7 but "casting out" 7s is easy because 7 is a single digit. Given 840539438261 has the divisibility as 140539438261 which has the same as 539438261 as 119438261 as 49438261 as 438261 as 18261 as 4261 as 61 is not divisible by 7. You can do the same for any number but it's easiest for 7. It's the only way I know for 13. A number is divisible by 11 if the sum of the even place digits is the same as the odd placed digits or off by a multiple of 11.
$endgroup$
– fleablood
Feb 29 '16 at 19:41
$begingroup$
@fleablood: another test I learned for 7-divisibility is to subtract 21 times the least digit and then divide by 10. That is to say, discard the least digit and then subtract double the digit you discarded. Hence 840539438261 -> 84053943824 -> 8405394374 -> 840539429 -> 84053924 -> 8405384 -> 840530 > 84053 -> 8399 -> 821 -> 80 -> 8, so not divisible by 7. Note this doesn't tell you the modulus, whereas casting out does. You can do a similar trick for 17 using 51 in place of 21, and 13 using 39 (i.e. add 4 times the digit you chopped off).
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:49
$begingroup$
@fleablood: another test I learned for 7-divisibility is to subtract 21 times the least digit and then divide by 10. That is to say, discard the least digit and then subtract double the digit you discarded. Hence 840539438261 -> 84053943824 -> 8405394374 -> 840539429 -> 84053924 -> 8405384 -> 840530 > 84053 -> 8399 -> 821 -> 80 -> 8, so not divisible by 7. Note this doesn't tell you the modulus, whereas casting out does. You can do a similar trick for 17 using 51 in place of 21, and 13 using 39 (i.e. add 4 times the digit you chopped off).
$endgroup$
– Steve Jessop
Mar 1 '16 at 11:49
$begingroup$
@SteveJessop don't understand. 840539438261 to 84053943824. Okay, that's just subtracting 21 and dividing by 10. 84053943824 to 8405394374. Okay the 2 is the least digit so we remove it. Then... the eight before the 2 becomes a 7????? why? Then 8405394374 to 840539429 ... so the 374 gets turned into 29? WTF?
$endgroup$
– fleablood
Mar 1 '16 at 17:04
$begingroup$
@SteveJessop don't understand. 840539438261 to 84053943824. Okay, that's just subtracting 21 and dividing by 10. 84053943824 to 8405394374. Okay the 2 is the least digit so we remove it. Then... the eight before the 2 becomes a 7????? why? Then 8405394374 to 840539429 ... so the 374 gets turned into 29? WTF?
$endgroup$
– fleablood
Mar 1 '16 at 17:04
$begingroup$
@fleablood: by "least digit" I mean "least significant digit", sorry. 84053943824, chop off the last digit would be 8405394382. The last digit was 4, so subtracting 8 from 8405394382 leaves 8405394374. The net result is that we have subtracted 21 * 4 and then divided by 10, both of which operations preserve divisibility by 7.
$endgroup$
– Steve Jessop
Mar 1 '16 at 17:07
$begingroup$
@fleablood: by "least digit" I mean "least significant digit", sorry. 84053943824, chop off the last digit would be 8405394382. The last digit was 4, so subtracting 8 from 8405394382 leaves 8405394374. The net result is that we have subtracted 21 * 4 and then divided by 10, both of which operations preserve divisibility by 7.
$endgroup$
– Steve Jessop
Mar 1 '16 at 17:07
$begingroup$
Hmmm... in my opinion multiplying and carrying is just as hard as doing a complete division. Casting out is faster and easier. Especially as we have 142 other numbers to test.
$endgroup$
– fleablood
Mar 1 '16 at 17:14
$begingroup$
Hmmm... in my opinion multiplying and carrying is just as hard as doing a complete division. Casting out is faster and easier. Especially as we have 142 other numbers to test.
$endgroup$
– fleablood
Mar 1 '16 at 17:14
add a comment |
$begingroup$
I'd probably recommend just knowing all your primes between 7-150.
Start with 7 and count by 2s. If it looks prime, name it. The 3 exceptions between 1-100 are 57, 87 and 91. (I'm assuming "77" and "93" don't look prime to you.)
Keep counting past 100 and write your guesses down. Then check them all by Googling a list of prime numbers. Whichever ones you got wrong, memorize. This won't be many because you'll guess most right.
answered Mar 1 '16 at 14:54
djechlindjechlin
4,8401230
$endgroup$
add a comment |
$begingroup$
I'd probably recommend just knowing all your primes between 7-150.
Start with 7 and count by 2s. If it looks prime, name it. The 3 exceptions between 1-100 are 57, 87 and 91. (I'm assuming "77" and "93" don't look prime to you.)
Keep counting past 100 and write your guesses down. Then check them all by Googling a list of prime numbers. Whichever ones you got wrong, memorize. This won't be many because you'll guess most right.
answered Mar 1 '16 at 14:54
djechlindjechlin
4,8401230
$endgroup$
add a comment |
$begingroup$
I'd probably recommend just knowing all your primes between 7-150.
Start with 7 and count by 2s. If it looks prime, name it. The 3 exceptions between 1-100 are 57, 87 and 91. (I'm assuming "77" and "93" don't look prime to you.)
Keep counting past 100 and write your guesses down. Then check them all by Googling a list of prime numbers. Whichever ones you got wrong, memorize. This won't be many because you'll guess most right.
answered Mar 1 '16 at 14:54
djechlindjechlin
4,8401230
$endgroup$
I'd probably recommend just knowing all your primes between 7-150.
Start with 7 and count by 2s. If it looks prime, name it. The 3 exceptions between 1-100 are 57, 87 and 91. (I'm assuming "77" and "93" don't look prime to you.)
Keep counting past 100 and write your guesses down. Then check them all by Googling a list of prime numbers. Whichever ones you got wrong, memorize. This won't be many because you'll guess most right.
answered Mar 1 '16 at 14:54
djechlindjechlin
4,8401230
answered Mar 1 '16 at 14:54
djechlindjechlin
4,8401230
answered Mar 1 '16 at 14:54
djechlindjechlin
4,8401230
answered Mar 1 '16 at 14:54
djechlindjechlin
4,8401230
4,8401230
add a comment |
add a comment |
$begingroup$
Prime numbers greater than 3 are of the form $6n pm 1$ , then you can test manually between 7 and 150. It will be easier than testing every odd integer as mentioned in other answer.
answered Mar 1 '16 at 15:08
Mojo JojoMojo Jojo
308112
$endgroup$
add a comment |
$begingroup$
Prime numbers greater than 3 are of the form $6n pm 1$ , then you can test manually between 7 and 150. It will be easier than testing every odd integer as mentioned in other answer.
answered Mar 1 '16 at 15:08
Mojo JojoMojo Jojo
308112
$endgroup$
add a comment |
$begingroup$
Prime numbers greater than 3 are of the form $6n pm 1$ , then you can test manually between 7 and 150. It will be easier than testing every odd integer as mentioned in other answer.
answered Mar 1 '16 at 15:08
Mojo JojoMojo Jojo
308112
$endgroup$
Prime numbers greater than 3 are of the form $6n pm 1$ , then you can test manually between 7 and 150. It will be easier than testing every odd integer as mentioned in other answer.
answered Mar 1 '16 at 15:08
Mojo JojoMojo Jojo
308112
edited Mar 1 '16 at 16:08
answered Mar 1 '16 at 15:08
Mojo JojoMojo Jojo
308112
answered Mar 1 '16 at 15:08
Mojo JojoMojo Jojo
308112
answered Mar 1 '16 at 15:08
Mojo JojoMojo Jojo
308112
308112
add a comment |
add a comment |
$begingroup$
There is no answer yet which points this out: A couple of years ago it was found that you can test for primality in polynomial time. See https://en.wikipedia.org/wiki/AKS_primality_test
answered Mar 1 '16 at 13:19
RobinRobin
1112
$endgroup$
$begingroup$
That's true, but given the OP is concerned with a 1-byte input, this breakthrough may not be terribly relevant :P
$endgroup$
– djechlin
Mar 1 '16 at 15:07
add a comment |
$begingroup$
There is no answer yet which points this out: A couple of years ago it was found that you can test for primality in polynomial time. See https://en.wikipedia.org/wiki/AKS_primality_test
answered Mar 1 '16 at 13:19
RobinRobin
1112
$endgroup$
$begingroup$
That's true, but given the OP is concerned with a 1-byte input, this breakthrough may not be terribly relevant :P
$endgroup$
– djechlin
Mar 1 '16 at 15:07
add a comment |
$begingroup$
There is no answer yet which points this out: A couple of years ago it was found that you can test for primality in polynomial time. See https://en.wikipedia.org/wiki/AKS_primality_test
answered Mar 1 '16 at 13:19
RobinRobin
1112
$endgroup$
There is no answer yet which points this out: A couple of years ago it was found that you can test for primality in polynomial time. See https://en.wikipedia.org/wiki/AKS_primality_test
answered Mar 1 '16 at 13:19
RobinRobin
1112
answered Mar 1 '16 at 13:19
RobinRobin
1112
answered Mar 1 '16 at 13:19
RobinRobin
1112
answered Mar 1 '16 at 13:19
RobinRobin
1112
1112
$begingroup$
That's true, but given the OP is concerned with a 1-byte input, this breakthrough may not be terribly relevant :P
$endgroup$
– djechlin
Mar 1 '16 at 15:07
add a comment |
$begingroup$
That's true, but given the OP is concerned with a 1-byte input, this breakthrough may not be terribly relevant :P
$endgroup$
– djechlin
Mar 1 '16 at 15:07
$begingroup$
That's true, but given the OP is concerned with a 1-byte input, this breakthrough may not be terribly relevant :P
$endgroup$
– djechlin
Mar 1 '16 at 15:07
$begingroup$
That's true, but given the OP is concerned with a 1-byte input, this breakthrough may not be terribly relevant :P
$endgroup$
– djechlin
Mar 1 '16 at 15:07
add a comment |
$begingroup$
Start with the square root of 150, the integer value is 12. Your prime divisors are 2 3 5 7 and 11. Eliminate the even numbers and the numbers ending in 5. The first test will be 3 squared or 9 in this case add 6 to 9 and so on to eliminate the 3s. The next test is 7 squared or 49 and this time add 14 to eliminate the 7s. The last test is 11 squared or 121 and this time add 22 to eliminate the 11s. The numbers left on your list should be prime numbers. Or Make a chart with 2, 3, 7, 9 on the left side and 0, 10, 20, 30 ..... 140 across the top. This eliminates the even numbers and numbers ending in 5. Then it's 3*3 = 9, 3*7 = 21, 3*9 = 27, 11*3 = 33 etc. Then 7*7 = 49, 7*11 = 77, 7*13 = 91 etc. Then 11*11 = 121
and 11*13 = 143 and the remaining numbers are prime.
answered Mar 2 '16 at 4:19
RayRay
393
$endgroup$
add a comment |
$begingroup$
Start with the square root of 150, the integer value is 12. Your prime divisors are 2 3 5 7 and 11. Eliminate the even numbers and the numbers ending in 5. The first test will be 3 squared or 9 in this case add 6 to 9 and so on to eliminate the 3s. The next test is 7 squared or 49 and this time add 14 to eliminate the 7s. The last test is 11 squared or 121 and this time add 22 to eliminate the 11s. The numbers left on your list should be prime numbers. Or Make a chart with 2, 3, 7, 9 on the left side and 0, 10, 20, 30 ..... 140 across the top. This eliminates the even numbers and numbers ending in 5. Then it's 3*3 = 9, 3*7 = 21, 3*9 = 27, 11*3 = 33 etc. Then 7*7 = 49, 7*11 = 77, 7*13 = 91 etc. Then 11*11 = 121
and 11*13 = 143 and the remaining numbers are prime.
answered Mar 2 '16 at 4:19
RayRay
393
$endgroup$
add a comment |
$begingroup$
Start with the square root of 150, the integer value is 12. Your prime divisors are 2 3 5 7 and 11. Eliminate the even numbers and the numbers ending in 5. The first test will be 3 squared or 9 in this case add 6 to 9 and so on to eliminate the 3s. The next test is 7 squared or 49 and this time add 14 to eliminate the 7s. The last test is 11 squared or 121 and this time add 22 to eliminate the 11s. The numbers left on your list should be prime numbers. Or Make a chart with 2, 3, 7, 9 on the left side and 0, 10, 20, 30 ..... 140 across the top. This eliminates the even numbers and numbers ending in 5. Then it's 3*3 = 9, 3*7 = 21, 3*9 = 27, 11*3 = 33 etc. Then 7*7 = 49, 7*11 = 77, 7*13 = 91 etc. Then 11*11 = 121
and 11*13 = 143 and the remaining numbers are prime.
answered Mar 2 '16 at 4:19
RayRay
393
$endgroup$
Start with the square root of 150, the integer value is 12. Your prime divisors are 2 3 5 7 and 11. Eliminate the even numbers and the numbers ending in 5. The first test will be 3 squared or 9 in this case add 6 to 9 and so on to eliminate the 3s. The next test is 7 squared or 49 and this time add 14 to eliminate the 7s. The last test is 11 squared or 121 and this time add 22 to eliminate the 11s. The numbers left on your list should be prime numbers. Or Make a chart with 2, 3, 7, 9 on the left side and 0, 10, 20, 30 ..... 140 across the top. This eliminates the even numbers and numbers ending in 5. Then it's 3*3 = 9, 3*7 = 21, 3*9 = 27, 11*3 = 33 etc. Then 7*7 = 49, 7*11 = 77, 7*13 = 91 etc. Then 11*11 = 121
and 11*13 = 143 and the remaining numbers are prime.
answered Mar 2 '16 at 4:19
RayRay
393
answered Mar 2 '16 at 4:19
RayRay
393
answered Mar 2 '16 at 4:19
RayRay
393
answered Mar 2 '16 at 4:19
RayRay
393
393
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%2f1676996%2ftests-for-prime-numbers%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
10
$begingroup$
en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– Mythomorphic
Feb 29 '16 at 12:29
1
$begingroup$
Check only numbers that are adjacent to multiples of $6$ (for example, $5$ and $7$, $11$ and $13$, etc).
$endgroup$
– barak manos
Feb 29 '16 at 12:31
4
$begingroup$
Is there a possible exam condition where you will be asked to list primes in such an interval?
$endgroup$
– Henning Makholm
Feb 29 '16 at 12:33
1
$begingroup$
There are many prime generating sieves and an entire theory domain.
$endgroup$
– user49763
Feb 29 '16 at 23:24
1
$begingroup$
Probably oral test... I had it once where each student had to move to front of the class and mentioned prime numbers from 1-100. (I remember I got tripped on 91)
$endgroup$
– Andrew T.
Mar 1 '16 at 10:00