Mixing
Is there a way to find the prime numbers up to 1000 with less than 200 calculations?
$begingroup$
By using a sieve created by Prime Number Tables set up by the formula PN+(PNx6) for numbers generated by 6n+or-1, takes 182 calculations to identify 170 composite numbers. Using the Sieve of Eratosthenes would take around 1600 calculations. The Prime Number Tables identify all the composite numbers on the the list of 332 possible prime numbers:
5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,101,107,113,119,125,131,137,143,149,155,161...
7,13,19,25,31,37,49,55,61,67,73,79,85,91,97,103,109,115,121,127,133,139,145,151,157,163,169...
Prime Number Table for:
5 identifies the multiples of 5 with 67 calculations (the Sieve of E: 249)
7: 23 calculations (the Sieve of E: 133)
11: 29 calculations (the Sieve of E: 98)
13: 11 calculations (the Sieve of E: 75)
17: 17 calculations (the Sieve of E: 57)
19: 4 calculations (the Sieve of E: 51)
23: 12 calculations (the Sieve of E: 42)
29: 5 calculations (the Sieve of E: 34)
31: 1 calculations (the Sieve of E: 31)
41: 3 47: 3 53: 2 59: 2 calculations (the Sieve of E:0)
71: 2 89: 1 101: 1 calculations (the Sieve of E: 0)
107: 1 113: 1 131: 1 137: 1 calculations (the Sieve of E: 0)
2: 0 calculations (the Sieve of E:499)
3: 0 calculations (the Sieve of E: 332)
Total Calculations:
A Sieve using PN Tables: 187 calculations to find 166 Prime Numbers by identifying 166 composite numbers (10 of 11 duplicate of multiples of 5)
Sieve of Eratosthenes: 1601 calculations to find 168 Prime Numbers by identifying 832 composite numbers (769 duplication of calculations)
Note: What I am really hoping for is some help. I have tested this up to 1411. There is no reason to believe it wouldn't go to whatever number. It seems since it deals with less numbers and less calculations, it would use less memory. If you look at the tables and what I have been able to research it makes Primes numbers even more interesting for children who might then take up more interest in math. Hey, I am a guy who works in a grocery store who just likes to think about things. I need help. People keep telling me about the Sieve of Eratosthenes. I have given a comparison between the 2 sieves. Would you rather make 1600 calculations or 187?
You can check on my website: https://mrspudgetty.wixsite.com/mr-spudgetty/prime-numbers
prime-numbers
asked Feb 1 at 11:35
Orlando VidadsOrlando Vidads
72
$endgroup$
add a comment |
$begingroup$
By using a sieve created by Prime Number Tables set up by the formula PN+(PNx6) for numbers generated by 6n+or-1, takes 182 calculations to identify 170 composite numbers. Using the Sieve of Eratosthenes would take around 1600 calculations. The Prime Number Tables identify all the composite numbers on the the list of 332 possible prime numbers:
5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,101,107,113,119,125,131,137,143,149,155,161...
7,13,19,25,31,37,49,55,61,67,73,79,85,91,97,103,109,115,121,127,133,139,145,151,157,163,169...
Prime Number Table for:
5 identifies the multiples of 5 with 67 calculations (the Sieve of E: 249)
7: 23 calculations (the Sieve of E: 133)
11: 29 calculations (the Sieve of E: 98)
13: 11 calculations (the Sieve of E: 75)
17: 17 calculations (the Sieve of E: 57)
19: 4 calculations (the Sieve of E: 51)
23: 12 calculations (the Sieve of E: 42)
29: 5 calculations (the Sieve of E: 34)
31: 1 calculations (the Sieve of E: 31)
41: 3 47: 3 53: 2 59: 2 calculations (the Sieve of E:0)
71: 2 89: 1 101: 1 calculations (the Sieve of E: 0)
107: 1 113: 1 131: 1 137: 1 calculations (the Sieve of E: 0)
2: 0 calculations (the Sieve of E:499)
3: 0 calculations (the Sieve of E: 332)
Total Calculations:
A Sieve using PN Tables: 187 calculations to find 166 Prime Numbers by identifying 166 composite numbers (10 of 11 duplicate of multiples of 5)
Sieve of Eratosthenes: 1601 calculations to find 168 Prime Numbers by identifying 832 composite numbers (769 duplication of calculations)
Note: What I am really hoping for is some help. I have tested this up to 1411. There is no reason to believe it wouldn't go to whatever number. It seems since it deals with less numbers and less calculations, it would use less memory. If you look at the tables and what I have been able to research it makes Primes numbers even more interesting for children who might then take up more interest in math. Hey, I am a guy who works in a grocery store who just likes to think about things. I need help. People keep telling me about the Sieve of Eratosthenes. I have given a comparison between the 2 sieves. Would you rather make 1600 calculations or 187?
You can check on my website: https://mrspudgetty.wixsite.com/mr-spudgetty/prime-numbers
prime-numbers
asked Feb 1 at 11:35
Orlando VidadsOrlando Vidads
72
$endgroup$
$begingroup$
"They are numbers that have 1 and the number itself as the only multiples": multiples should be divisors.
$endgroup$
– TonyK
Feb 1 at 11:47
$begingroup$
Thanks you. I may not have worded the question clearly. I am wondering if there is a way, such as the sieve of Eratosthenes, that would use less than 200 calculations to eliminate all of the composite numbers up to 1000. The Sieve mentioned uses around 1600 to identify 832 composite number. The calculations for 2 and 3 alone are 831. I was hoping others might look over a process I stumbled into that takes only 187 calculation to find all the prime numbers (168 Total) up to the 1000 mark.
$endgroup$
– Orlando Vidads
Feb 1 at 22:17
$begingroup$
Yes, I get that. And I took a brief look at your web site, but it wasn't clear to me what you were doing. But I did notice that error that I commented on, and I thought you might like to be informed.
$endgroup$
– TonyK
Feb 1 at 22:35
$begingroup$
Ok Thanks. Yes maybe that is the problem I am having. I stumbled into this making a table for 5, by lining up the sequence of the numbers 5, 6, 7 with the sequence 35, 36, 37. By adding 30 the multiples of 5 lined up in a column. Another column of composite numbers lined up as well at 25. So, in the first column, the table had 5 35 65 95 125. The other column had 25 55 85 115. Those were the same multiples in the sequence of 6n+or-1. I realized 30 I had added to each row was PNx6. So, for 7,the results were 49 91 133 175. For 11: 77 143 209 ... Each number matched a number on the list.
$endgroup$
– Orlando Vidads
Feb 2 at 0:33
add a comment |
$begingroup$
By using a sieve created by Prime Number Tables set up by the formula PN+(PNx6) for numbers generated by 6n+or-1, takes 182 calculations to identify 170 composite numbers. Using the Sieve of Eratosthenes would take around 1600 calculations. The Prime Number Tables identify all the composite numbers on the the list of 332 possible prime numbers:
5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,101,107,113,119,125,131,137,143,149,155,161...
7,13,19,25,31,37,49,55,61,67,73,79,85,91,97,103,109,115,121,127,133,139,145,151,157,163,169...
Prime Number Table for:
5 identifies the multiples of 5 with 67 calculations (the Sieve of E: 249)
7: 23 calculations (the Sieve of E: 133)
11: 29 calculations (the Sieve of E: 98)
13: 11 calculations (the Sieve of E: 75)
17: 17 calculations (the Sieve of E: 57)
19: 4 calculations (the Sieve of E: 51)
23: 12 calculations (the Sieve of E: 42)
29: 5 calculations (the Sieve of E: 34)
31: 1 calculations (the Sieve of E: 31)
41: 3 47: 3 53: 2 59: 2 calculations (the Sieve of E:0)
71: 2 89: 1 101: 1 calculations (the Sieve of E: 0)
107: 1 113: 1 131: 1 137: 1 calculations (the Sieve of E: 0)
2: 0 calculations (the Sieve of E:499)
3: 0 calculations (the Sieve of E: 332)
Total Calculations:
A Sieve using PN Tables: 187 calculations to find 166 Prime Numbers by identifying 166 composite numbers (10 of 11 duplicate of multiples of 5)
Sieve of Eratosthenes: 1601 calculations to find 168 Prime Numbers by identifying 832 composite numbers (769 duplication of calculations)
Note: What I am really hoping for is some help. I have tested this up to 1411. There is no reason to believe it wouldn't go to whatever number. It seems since it deals with less numbers and less calculations, it would use less memory. If you look at the tables and what I have been able to research it makes Primes numbers even more interesting for children who might then take up more interest in math. Hey, I am a guy who works in a grocery store who just likes to think about things. I need help. People keep telling me about the Sieve of Eratosthenes. I have given a comparison between the 2 sieves. Would you rather make 1600 calculations or 187?
You can check on my website: https://mrspudgetty.wixsite.com/mr-spudgetty/prime-numbers
prime-numbers
asked Feb 1 at 11:35
Orlando VidadsOrlando Vidads
72
$endgroup$
By using a sieve created by Prime Number Tables set up by the formula PN+(PNx6) for numbers generated by 6n+or-1, takes 182 calculations to identify 170 composite numbers. Using the Sieve of Eratosthenes would take around 1600 calculations. The Prime Number Tables identify all the composite numbers on the the list of 332 possible prime numbers:
5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,101,107,113,119,125,131,137,143,149,155,161...
7,13,19,25,31,37,49,55,61,67,73,79,85,91,97,103,109,115,121,127,133,139,145,151,157,163,169...
Prime Number Table for:
5 identifies the multiples of 5 with 67 calculations (the Sieve of E: 249)
7: 23 calculations (the Sieve of E: 133)
11: 29 calculations (the Sieve of E: 98)
13: 11 calculations (the Sieve of E: 75)
17: 17 calculations (the Sieve of E: 57)
19: 4 calculations (the Sieve of E: 51)
23: 12 calculations (the Sieve of E: 42)
29: 5 calculations (the Sieve of E: 34)
31: 1 calculations (the Sieve of E: 31)
41: 3 47: 3 53: 2 59: 2 calculations (the Sieve of E:0)
71: 2 89: 1 101: 1 calculations (the Sieve of E: 0)
107: 1 113: 1 131: 1 137: 1 calculations (the Sieve of E: 0)
2: 0 calculations (the Sieve of E:499)
3: 0 calculations (the Sieve of E: 332)
Total Calculations:
A Sieve using PN Tables: 187 calculations to find 166 Prime Numbers by identifying 166 composite numbers (10 of 11 duplicate of multiples of 5)
Sieve of Eratosthenes: 1601 calculations to find 168 Prime Numbers by identifying 832 composite numbers (769 duplication of calculations)
Note: What I am really hoping for is some help. I have tested this up to 1411. There is no reason to believe it wouldn't go to whatever number. It seems since it deals with less numbers and less calculations, it would use less memory. If you look at the tables and what I have been able to research it makes Primes numbers even more interesting for children who might then take up more interest in math. Hey, I am a guy who works in a grocery store who just likes to think about things. I need help. People keep telling me about the Sieve of Eratosthenes. I have given a comparison between the 2 sieves. Would you rather make 1600 calculations or 187?
You can check on my website: https://mrspudgetty.wixsite.com/mr-spudgetty/prime-numbers
prime-numbers
prime-numbers
asked Feb 1 at 11:35
Orlando VidadsOrlando Vidads
72
asked Feb 1 at 11:35
Orlando VidadsOrlando Vidads
72
asked Feb 1 at 11:35
Orlando VidadsOrlando Vidads
72
asked Feb 1 at 11:35
Orlando VidadsOrlando Vidads
72
asked Feb 1 at 11:35
Orlando VidadsOrlando Vidads
72
72
$begingroup$
"They are numbers that have 1 and the number itself as the only multiples": multiples should be divisors.
$endgroup$
– TonyK
Feb 1 at 11:47
$begingroup$
Thanks you. I may not have worded the question clearly. I am wondering if there is a way, such as the sieve of Eratosthenes, that would use less than 200 calculations to eliminate all of the composite numbers up to 1000. The Sieve mentioned uses around 1600 to identify 832 composite number. The calculations for 2 and 3 alone are 831. I was hoping others might look over a process I stumbled into that takes only 187 calculation to find all the prime numbers (168 Total) up to the 1000 mark.
$endgroup$
– Orlando Vidads
Feb 1 at 22:17
$begingroup$
Yes, I get that. And I took a brief look at your web site, but it wasn't clear to me what you were doing. But I did notice that error that I commented on, and I thought you might like to be informed.
$endgroup$
– TonyK
Feb 1 at 22:35
$begingroup$
Ok Thanks. Yes maybe that is the problem I am having. I stumbled into this making a table for 5, by lining up the sequence of the numbers 5, 6, 7 with the sequence 35, 36, 37. By adding 30 the multiples of 5 lined up in a column. Another column of composite numbers lined up as well at 25. So, in the first column, the table had 5 35 65 95 125. The other column had 25 55 85 115. Those were the same multiples in the sequence of 6n+or-1. I realized 30 I had added to each row was PNx6. So, for 7,the results were 49 91 133 175. For 11: 77 143 209 ... Each number matched a number on the list.
$endgroup$
– Orlando Vidads
Feb 2 at 0:33
add a comment |
$begingroup$
"They are numbers that have 1 and the number itself as the only multiples": multiples should be divisors.
$endgroup$
– TonyK
Feb 1 at 11:47
$begingroup$
Thanks you. I may not have worded the question clearly. I am wondering if there is a way, such as the sieve of Eratosthenes, that would use less than 200 calculations to eliminate all of the composite numbers up to 1000. The Sieve mentioned uses around 1600 to identify 832 composite number. The calculations for 2 and 3 alone are 831. I was hoping others might look over a process I stumbled into that takes only 187 calculation to find all the prime numbers (168 Total) up to the 1000 mark.
$endgroup$
– Orlando Vidads
Feb 1 at 22:17
$begingroup$
Yes, I get that. And I took a brief look at your web site, but it wasn't clear to me what you were doing. But I did notice that error that I commented on, and I thought you might like to be informed.
$endgroup$
– TonyK
Feb 1 at 22:35
$begingroup$
Ok Thanks. Yes maybe that is the problem I am having. I stumbled into this making a table for 5, by lining up the sequence of the numbers 5, 6, 7 with the sequence 35, 36, 37. By adding 30 the multiples of 5 lined up in a column. Another column of composite numbers lined up as well at 25. So, in the first column, the table had 5 35 65 95 125. The other column had 25 55 85 115. Those were the same multiples in the sequence of 6n+or-1. I realized 30 I had added to each row was PNx6. So, for 7,the results were 49 91 133 175. For 11: 77 143 209 ... Each number matched a number on the list.
$endgroup$
– Orlando Vidads
Feb 2 at 0:33
$begingroup$
"They are numbers that have 1 and the number itself as the only multiples": multiples should be divisors.
$endgroup$
– TonyK
Feb 1 at 11:47
$begingroup$
"They are numbers that have 1 and the number itself as the only multiples": multiples should be divisors.
$endgroup$
– TonyK
Feb 1 at 11:47
$begingroup$
Thanks you. I may not have worded the question clearly. I am wondering if there is a way, such as the sieve of Eratosthenes, that would use less than 200 calculations to eliminate all of the composite numbers up to 1000. The Sieve mentioned uses around 1600 to identify 832 composite number. The calculations for 2 and 3 alone are 831. I was hoping others might look over a process I stumbled into that takes only 187 calculation to find all the prime numbers (168 Total) up to the 1000 mark.
$endgroup$
– Orlando Vidads
Feb 1 at 22:17
$begingroup$
Thanks you. I may not have worded the question clearly. I am wondering if there is a way, such as the sieve of Eratosthenes, that would use less than 200 calculations to eliminate all of the composite numbers up to 1000. The Sieve mentioned uses around 1600 to identify 832 composite number. The calculations for 2 and 3 alone are 831. I was hoping others might look over a process I stumbled into that takes only 187 calculation to find all the prime numbers (168 Total) up to the 1000 mark.
$endgroup$
– Orlando Vidads
Feb 1 at 22:17
$begingroup$
Yes, I get that. And I took a brief look at your web site, but it wasn't clear to me what you were doing. But I did notice that error that I commented on, and I thought you might like to be informed.
$endgroup$
– TonyK
Feb 1 at 22:35
$begingroup$
Yes, I get that. And I took a brief look at your web site, but it wasn't clear to me what you were doing. But I did notice that error that I commented on, and I thought you might like to be informed.
$endgroup$
– TonyK
Feb 1 at 22:35
$begingroup$
Ok Thanks. Yes maybe that is the problem I am having. I stumbled into this making a table for 5, by lining up the sequence of the numbers 5, 6, 7 with the sequence 35, 36, 37. By adding 30 the multiples of 5 lined up in a column. Another column of composite numbers lined up as well at 25. So, in the first column, the table had 5 35 65 95 125. The other column had 25 55 85 115. Those were the same multiples in the sequence of 6n+or-1. I realized 30 I had added to each row was PNx6. So, for 7,the results were 49 91 133 175. For 11: 77 143 209 ... Each number matched a number on the list.
$endgroup$
– Orlando Vidads
Feb 2 at 0:33
$begingroup$
Ok Thanks. Yes maybe that is the problem I am having. I stumbled into this making a table for 5, by lining up the sequence of the numbers 5, 6, 7 with the sequence 35, 36, 37. By adding 30 the multiples of 5 lined up in a column. Another column of composite numbers lined up as well at 25. So, in the first column, the table had 5 35 65 95 125. The other column had 25 55 85 115. Those were the same multiples in the sequence of 6n+or-1. I realized 30 I had added to each row was PNx6. So, for 7,the results were 49 91 133 175. For 11: 77 143 209 ... Each number matched a number on the list.
$endgroup$
– Orlando Vidads
Feb 2 at 0:33
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
What you are looking for is a computational function that returns the list of primes less than 1000, and works as efficiently as possible, on just that problem.
There are 168 primes between 1 and 1000, so any method will take at least 168 operations, obviously.
Suppose you could find approximately a list of 13 numbers and a disjoint other list of 13 numbers, such that precisely every prime occurs when you sum the two sets together elementwise, and no more than that (no composites; otherwise more testing would be required to filter them out).
What I mean is:
$$
A := {0, 2, 6} \
B := {5, 11, 17} \
A + B = { 5, 11, 17, 7, 13, 19, 23}
$$
You can most likely find two sets of around 13-20 elements each such that when you sum the sets you get your list. The sets would then be constants in your program, and the program that generates your output in under 200 operations, actually in 169 arithmetic operations (less if you're allowed to include $B$ which could be made to be all prime numbers if there's a $0$ included in $A$).
See:
Compressing the primes using addition
answered Feb 2 at 8:39
BananaCatsBananaCats
9,36252659
$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%2f3096115%2fis-there-a-way-to-find-the-prime-numbers-up-to-1000-with-less-than-200-calculati%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
What you are looking for is a computational function that returns the list of primes less than 1000, and works as efficiently as possible, on just that problem.
There are 168 primes between 1 and 1000, so any method will take at least 168 operations, obviously.
Suppose you could find approximately a list of 13 numbers and a disjoint other list of 13 numbers, such that precisely every prime occurs when you sum the two sets together elementwise, and no more than that (no composites; otherwise more testing would be required to filter them out).
What I mean is:
$$
A := {0, 2, 6} \
B := {5, 11, 17} \
A + B = { 5, 11, 17, 7, 13, 19, 23}
$$
You can most likely find two sets of around 13-20 elements each such that when you sum the sets you get your list. The sets would then be constants in your program, and the program that generates your output in under 200 operations, actually in 169 arithmetic operations (less if you're allowed to include $B$ which could be made to be all prime numbers if there's a $0$ included in $A$).
See:
Compressing the primes using addition
answered Feb 2 at 8:39
BananaCatsBananaCats
9,36252659
$endgroup$
add a comment |
$begingroup$
What you are looking for is a computational function that returns the list of primes less than 1000, and works as efficiently as possible, on just that problem.
There are 168 primes between 1 and 1000, so any method will take at least 168 operations, obviously.
Suppose you could find approximately a list of 13 numbers and a disjoint other list of 13 numbers, such that precisely every prime occurs when you sum the two sets together elementwise, and no more than that (no composites; otherwise more testing would be required to filter them out).
What I mean is:
$$
A := {0, 2, 6} \
B := {5, 11, 17} \
A + B = { 5, 11, 17, 7, 13, 19, 23}
$$
You can most likely find two sets of around 13-20 elements each such that when you sum the sets you get your list. The sets would then be constants in your program, and the program that generates your output in under 200 operations, actually in 169 arithmetic operations (less if you're allowed to include $B$ which could be made to be all prime numbers if there's a $0$ included in $A$).
See:
Compressing the primes using addition
answered Feb 2 at 8:39
BananaCatsBananaCats
9,36252659
$endgroup$
add a comment |
$begingroup$
What you are looking for is a computational function that returns the list of primes less than 1000, and works as efficiently as possible, on just that problem.
There are 168 primes between 1 and 1000, so any method will take at least 168 operations, obviously.
Suppose you could find approximately a list of 13 numbers and a disjoint other list of 13 numbers, such that precisely every prime occurs when you sum the two sets together elementwise, and no more than that (no composites; otherwise more testing would be required to filter them out).
What I mean is:
$$
A := {0, 2, 6} \
B := {5, 11, 17} \
A + B = { 5, 11, 17, 7, 13, 19, 23}
$$
You can most likely find two sets of around 13-20 elements each such that when you sum the sets you get your list. The sets would then be constants in your program, and the program that generates your output in under 200 operations, actually in 169 arithmetic operations (less if you're allowed to include $B$ which could be made to be all prime numbers if there's a $0$ included in $A$).
See:
Compressing the primes using addition
answered Feb 2 at 8:39
BananaCatsBananaCats
9,36252659
$endgroup$
What you are looking for is a computational function that returns the list of primes less than 1000, and works as efficiently as possible, on just that problem.
There are 168 primes between 1 and 1000, so any method will take at least 168 operations, obviously.
Suppose you could find approximately a list of 13 numbers and a disjoint other list of 13 numbers, such that precisely every prime occurs when you sum the two sets together elementwise, and no more than that (no composites; otherwise more testing would be required to filter them out).
What I mean is:
$$
A := {0, 2, 6} \
B := {5, 11, 17} \
A + B = { 5, 11, 17, 7, 13, 19, 23}
$$
You can most likely find two sets of around 13-20 elements each such that when you sum the sets you get your list. The sets would then be constants in your program, and the program that generates your output in under 200 operations, actually in 169 arithmetic operations (less if you're allowed to include $B$ which could be made to be all prime numbers if there's a $0$ included in $A$).
See:
Compressing the primes using addition
answered Feb 2 at 8:39
BananaCatsBananaCats
9,36252659
edited Feb 2 at 8:47
answered Feb 2 at 8:39
BananaCatsBananaCats
9,36252659
answered Feb 2 at 8:39
BananaCatsBananaCats
9,36252659
answered Feb 2 at 8:39
BananaCatsBananaCats
9,36252659
9,36252659
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%2f3096115%2fis-there-a-way-to-find-the-prime-numbers-up-to-1000-with-less-than-200-calculati%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
$begingroup$
"They are numbers that have 1 and the number itself as the only multiples": multiples should be divisors.
$endgroup$
– TonyK
Feb 1 at 11:47
$begingroup$
Thanks you. I may not have worded the question clearly. I am wondering if there is a way, such as the sieve of Eratosthenes, that would use less than 200 calculations to eliminate all of the composite numbers up to 1000. The Sieve mentioned uses around 1600 to identify 832 composite number. The calculations for 2 and 3 alone are 831. I was hoping others might look over a process I stumbled into that takes only 187 calculation to find all the prime numbers (168 Total) up to the 1000 mark.
$endgroup$
– Orlando Vidads
Feb 1 at 22:17
$begingroup$
Yes, I get that. And I took a brief look at your web site, but it wasn't clear to me what you were doing. But I did notice that error that I commented on, and I thought you might like to be informed.
$endgroup$
– TonyK
Feb 1 at 22:35
$begingroup$
Ok Thanks. Yes maybe that is the problem I am having. I stumbled into this making a table for 5, by lining up the sequence of the numbers 5, 6, 7 with the sequence 35, 36, 37. By adding 30 the multiples of 5 lined up in a column. Another column of composite numbers lined up as well at 25. So, in the first column, the table had 5 35 65 95 125. The other column had 25 55 85 115. Those were the same multiples in the sequence of 6n+or-1. I realized 30 I had added to each row was PNx6. So, for 7,the results were 49 91 133 175. For 11: 77 143 209 ... Each number matched a number on the list.
$endgroup$
– Orlando Vidads
Feb 2 at 0:33