Is this an efficient type of sieve?
$begingroup$
Let $f(n)$ be the nth number of the form $6kpm1$, which can be defined by $f(n) = 3n + frac{3}{2} - frac{(-1)^n}{2}$.
Now $f(n)$ obviously outputs all primes $p gt3$, but also composite numbers whose factors were previously given by $f(n)$. (In other words, a composite number produced by $f(n)$ never has 2 or 3 as a factor.)
A way of avoiding these composites is based on a growing set of simple modulo-rules and the previous outputs of $f(n)$:
Given $f(n) = a$, where $a$ is prime, every following input $n^*$ which satisfies
$n^* equiv npmod{2a}$ or $n^* equiv b_npmod{2a}$ will output a composite with $a$ as a factor, where $b_n$ is the nth element of the sequence ${8,11,18,21,28,31,38,41,48,...}$
(Please bear with me, I'm afraid this part is a bit confusing to get across, so I'll give with some examples)
$f(1) = 5$, so every following $n$ which is $equiv 1pmod{10}$ or $equiv 8pmod{10}$ will produce a composite with 5 as a factor.
$f(2) = 7$, so every following $n$ which is $equiv 2pmod{14}$ or $equiv 11pmod{14}$ will produce a composite with 7 as a factor.
$f(3) = 11$, so every following $n$ which is $equiv 3pmod{22}$ or $equiv 18pmod{22}$ will produce a composite with 11 as a factor.
$f(4) = 13$, so every following $n$ which is $equiv 4pmod{26}$ or $equiv 21pmod{26}$ will produce a composite with 13 as a factor.
My main question is:
Is this an efficient type of sieve? Because it knows no upper bounds, outputs every prime $pgt3$ without skipping any and the next input is given by a set of modulo-rules, which should be fast to compute.
My side question is: Is it possible to derive a fomula for every modulo-rule like $f(n)$ for $6kpm1$? (With that I mean to create a formula which outputs all numbers which satisfy the rule)
prime-numbers
asked Dec 31 '18 at 15:33
g3nuineg3nuine
1598
$endgroup$
add a comment |
$begingroup$
Let $f(n)$ be the nth number of the form $6kpm1$, which can be defined by $f(n) = 3n + frac{3}{2} - frac{(-1)^n}{2}$.
Now $f(n)$ obviously outputs all primes $p gt3$, but also composite numbers whose factors were previously given by $f(n)$. (In other words, a composite number produced by $f(n)$ never has 2 or 3 as a factor.)
A way of avoiding these composites is based on a growing set of simple modulo-rules and the previous outputs of $f(n)$:
Given $f(n) = a$, where $a$ is prime, every following input $n^*$ which satisfies
$n^* equiv npmod{2a}$ or $n^* equiv b_npmod{2a}$ will output a composite with $a$ as a factor, where $b_n$ is the nth element of the sequence ${8,11,18,21,28,31,38,41,48,...}$
(Please bear with me, I'm afraid this part is a bit confusing to get across, so I'll give with some examples)
$f(1) = 5$, so every following $n$ which is $equiv 1pmod{10}$ or $equiv 8pmod{10}$ will produce a composite with 5 as a factor.
$f(2) = 7$, so every following $n$ which is $equiv 2pmod{14}$ or $equiv 11pmod{14}$ will produce a composite with 7 as a factor.
$f(3) = 11$, so every following $n$ which is $equiv 3pmod{22}$ or $equiv 18pmod{22}$ will produce a composite with 11 as a factor.
$f(4) = 13$, so every following $n$ which is $equiv 4pmod{26}$ or $equiv 21pmod{26}$ will produce a composite with 13 as a factor.
My main question is:
Is this an efficient type of sieve? Because it knows no upper bounds, outputs every prime $pgt3$ without skipping any and the next input is given by a set of modulo-rules, which should be fast to compute.
My side question is: Is it possible to derive a fomula for every modulo-rule like $f(n)$ for $6kpm1$? (With that I mean to create a formula which outputs all numbers which satisfy the rule)
prime-numbers
asked Dec 31 '18 at 15:33
g3nuineg3nuine
1598
$endgroup$
$begingroup$
What is the point of your $p$, $q$, $r$ functions? You don't seem to be using those particular expressions for anything and it would be vastly simpler just to say that $f(n)$ is the $n$th number of the form $6kpm 1$.
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:43
1
$begingroup$
(Or, if you insist of having an arithmetic-looking formula for some reason, $f(n)=3n+3/2-(-1)^n/2$).
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:47
$begingroup$
Yes thats way better thanks
$endgroup$
– g3nuine
Dec 31 '18 at 15:51
add a comment |
$begingroup$
Let $f(n)$ be the nth number of the form $6kpm1$, which can be defined by $f(n) = 3n + frac{3}{2} - frac{(-1)^n}{2}$.
Now $f(n)$ obviously outputs all primes $p gt3$, but also composite numbers whose factors were previously given by $f(n)$. (In other words, a composite number produced by $f(n)$ never has 2 or 3 as a factor.)
A way of avoiding these composites is based on a growing set of simple modulo-rules and the previous outputs of $f(n)$:
Given $f(n) = a$, where $a$ is prime, every following input $n^*$ which satisfies
$n^* equiv npmod{2a}$ or $n^* equiv b_npmod{2a}$ will output a composite with $a$ as a factor, where $b_n$ is the nth element of the sequence ${8,11,18,21,28,31,38,41,48,...}$
(Please bear with me, I'm afraid this part is a bit confusing to get across, so I'll give with some examples)
$f(1) = 5$, so every following $n$ which is $equiv 1pmod{10}$ or $equiv 8pmod{10}$ will produce a composite with 5 as a factor.
$f(2) = 7$, so every following $n$ which is $equiv 2pmod{14}$ or $equiv 11pmod{14}$ will produce a composite with 7 as a factor.
$f(3) = 11$, so every following $n$ which is $equiv 3pmod{22}$ or $equiv 18pmod{22}$ will produce a composite with 11 as a factor.
$f(4) = 13$, so every following $n$ which is $equiv 4pmod{26}$ or $equiv 21pmod{26}$ will produce a composite with 13 as a factor.
My main question is:
Is this an efficient type of sieve? Because it knows no upper bounds, outputs every prime $pgt3$ without skipping any and the next input is given by a set of modulo-rules, which should be fast to compute.
My side question is: Is it possible to derive a fomula for every modulo-rule like $f(n)$ for $6kpm1$? (With that I mean to create a formula which outputs all numbers which satisfy the rule)
prime-numbers
asked Dec 31 '18 at 15:33
g3nuineg3nuine
1598
$endgroup$
Let $f(n)$ be the nth number of the form $6kpm1$, which can be defined by $f(n) = 3n + frac{3}{2} - frac{(-1)^n}{2}$.
Now $f(n)$ obviously outputs all primes $p gt3$, but also composite numbers whose factors were previously given by $f(n)$. (In other words, a composite number produced by $f(n)$ never has 2 or 3 as a factor.)
A way of avoiding these composites is based on a growing set of simple modulo-rules and the previous outputs of $f(n)$:
Given $f(n) = a$, where $a$ is prime, every following input $n^*$ which satisfies
$n^* equiv npmod{2a}$ or $n^* equiv b_npmod{2a}$ will output a composite with $a$ as a factor, where $b_n$ is the nth element of the sequence ${8,11,18,21,28,31,38,41,48,...}$
(Please bear with me, I'm afraid this part is a bit confusing to get across, so I'll give with some examples)
$f(1) = 5$, so every following $n$ which is $equiv 1pmod{10}$ or $equiv 8pmod{10}$ will produce a composite with 5 as a factor.
$f(2) = 7$, so every following $n$ which is $equiv 2pmod{14}$ or $equiv 11pmod{14}$ will produce a composite with 7 as a factor.
$f(3) = 11$, so every following $n$ which is $equiv 3pmod{22}$ or $equiv 18pmod{22}$ will produce a composite with 11 as a factor.
$f(4) = 13$, so every following $n$ which is $equiv 4pmod{26}$ or $equiv 21pmod{26}$ will produce a composite with 13 as a factor.
My main question is:
Is this an efficient type of sieve? Because it knows no upper bounds, outputs every prime $pgt3$ without skipping any and the next input is given by a set of modulo-rules, which should be fast to compute.
My side question is: Is it possible to derive a fomula for every modulo-rule like $f(n)$ for $6kpm1$? (With that I mean to create a formula which outputs all numbers which satisfy the rule)
prime-numbers
prime-numbers
asked Dec 31 '18 at 15:33
g3nuineg3nuine
1598
asked Dec 31 '18 at 15:33
g3nuineg3nuine
1598
edited Dec 31 '18 at 15:50
g3nuine
asked Dec 31 '18 at 15:33
g3nuineg3nuine
1598
asked Dec 31 '18 at 15:33
g3nuineg3nuine
1598
asked Dec 31 '18 at 15:33
g3nuineg3nuine
1598
1598
$begingroup$
What is the point of your $p$, $q$, $r$ functions? You don't seem to be using those particular expressions for anything and it would be vastly simpler just to say that $f(n)$ is the $n$th number of the form $6kpm 1$.
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:43
1
$begingroup$
(Or, if you insist of having an arithmetic-looking formula for some reason, $f(n)=3n+3/2-(-1)^n/2$).
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:47
$begingroup$
Yes thats way better thanks
$endgroup$
– g3nuine
Dec 31 '18 at 15:51
add a comment |
$begingroup$
What is the point of your $p$, $q$, $r$ functions? You don't seem to be using those particular expressions for anything and it would be vastly simpler just to say that $f(n)$ is the $n$th number of the form $6kpm 1$.
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:43
1
$begingroup$
(Or, if you insist of having an arithmetic-looking formula for some reason, $f(n)=3n+3/2-(-1)^n/2$).
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:47
$begingroup$
Yes thats way better thanks
$endgroup$
– g3nuine
Dec 31 '18 at 15:51
$begingroup$
What is the point of your $p$, $q$, $r$ functions? You don't seem to be using those particular expressions for anything and it would be vastly simpler just to say that $f(n)$ is the $n$th number of the form $6kpm 1$.
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:43
$begingroup$
What is the point of your $p$, $q$, $r$ functions? You don't seem to be using those particular expressions for anything and it would be vastly simpler just to say that $f(n)$ is the $n$th number of the form $6kpm 1$.
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:43
1
1
$begingroup$
(Or, if you insist of having an arithmetic-looking formula for some reason, $f(n)=3n+3/2-(-1)^n/2$).
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:47
$begingroup$
(Or, if you insist of having an arithmetic-looking formula for some reason, $f(n)=3n+3/2-(-1)^n/2$).
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:47
$begingroup$
Yes thats way better thanks
$endgroup$
– g3nuine
Dec 31 '18 at 15:51
$begingroup$
Yes thats way better thanks
$endgroup$
– g3nuine
Dec 31 '18 at 15:51
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You have an interesting idea. However, regarding your question about it being efficient, if you mean compared to the current state of the art prime generating algorithms, then I believe the answer is unfortunately no. Note I am not an expert myself regarding the various algorithms used for generating primes, but I'm currently doing some prime research so I have investigated what method might work best for me, and have implemented plus optimized a basic solution, so I have some knowledge about this area.
Note your formula to determine composites uses up to $2$ modulus calculations to check whether or not a value is a multiple of each prime. This could be made somewhat more efficient by just getting the integer remainder and then using it to do the $2$ comparisons. However, modulus operations are not particularly efficient apart from using certain constants that a good optimizing compiler will do more efficiently in certain cases (e.g., a bit shift for a power of 2). Instead, according to Optimizing software in C++, in section 14.5 Integer Division, it says "Integer division takes much longer time than addition, subtraction and multiplication (27 - 80 clock cycles for 32 - bit integers, depending on the processor)".
As for reducing the number of values to check, among the odd integers, using just $6k pm 1$ means you are only bypassing the ones of the form $6k + 3$, so you are checking $frac{2}{3}$ of them. However, with various Wheel factorization methods, you can get a considerably better reduction in the number of values to check, so at least some of the fastest prime generation algorithms use this.
Another important issue, especially for modern computers, that many people are not aware of is the degree that the amount of memory your program is actively using compared to how much & how fast your memory cache can affect the overall speed. Although processor speeds have improved considerably, at least up until a few years ago, memory speeds have not improved as much since about $10$ or $15$ years ago, so the memory cache has become a more important issue. In fact, due to the nature of what I'm doing, I estimate that it affects around $70$ or $80$ percent of my program speed. With your algorithm, you could store all of the $b_n$ values in memory, which would use more of the memory cache, or just calculate the second value from the first, but this will take some more processor time instead.
For my research, I found & adapted a fairly basic, but relatively efficient, Segmented sieve of Eratosthenes. Although it is fairly good as it is, I made it more efficient by replacing C++ vectors with C type fixed arrays, using bits to store certain values instead of bytes (to help with the memory cache issue), etc. Nonetheless, note that the PrimeSieve library which this originally came from is now much more efficient, but I didn't use it for various reasons of adaptability, complete confidence in understanding it, easy distribution of it, etc., with the segmented sieve being efficient enough (especially after my enhancements) for my purposes.
As for your side question, I have not checked into it to any extent, but I believe it would be possible to derive other modulo type checks.
Good luck with your investigations into methods to generate prime numbers. I hope that you someday find an improvement to the state of art methods.
answered Dec 31 '18 at 20:32
John OmielanJohn Omielan
4,1962215
$endgroup$
$begingroup$
Thank you for this comprehensive answer and your kind words. Although I doubt to find an improvement to the state of the art anytime I enjoy wasting my time with primes
$endgroup$
– g3nuine
Jan 3 at 0:35
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%2f3057813%2fis-this-an-efficient-type-of-sieve%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$
You have an interesting idea. However, regarding your question about it being efficient, if you mean compared to the current state of the art prime generating algorithms, then I believe the answer is unfortunately no. Note I am not an expert myself regarding the various algorithms used for generating primes, but I'm currently doing some prime research so I have investigated what method might work best for me, and have implemented plus optimized a basic solution, so I have some knowledge about this area.
Note your formula to determine composites uses up to $2$ modulus calculations to check whether or not a value is a multiple of each prime. This could be made somewhat more efficient by just getting the integer remainder and then using it to do the $2$ comparisons. However, modulus operations are not particularly efficient apart from using certain constants that a good optimizing compiler will do more efficiently in certain cases (e.g., a bit shift for a power of 2). Instead, according to Optimizing software in C++, in section 14.5 Integer Division, it says "Integer division takes much longer time than addition, subtraction and multiplication (27 - 80 clock cycles for 32 - bit integers, depending on the processor)".
As for reducing the number of values to check, among the odd integers, using just $6k pm 1$ means you are only bypassing the ones of the form $6k + 3$, so you are checking $frac{2}{3}$ of them. However, with various Wheel factorization methods, you can get a considerably better reduction in the number of values to check, so at least some of the fastest prime generation algorithms use this.
Another important issue, especially for modern computers, that many people are not aware of is the degree that the amount of memory your program is actively using compared to how much & how fast your memory cache can affect the overall speed. Although processor speeds have improved considerably, at least up until a few years ago, memory speeds have not improved as much since about $10$ or $15$ years ago, so the memory cache has become a more important issue. In fact, due to the nature of what I'm doing, I estimate that it affects around $70$ or $80$ percent of my program speed. With your algorithm, you could store all of the $b_n$ values in memory, which would use more of the memory cache, or just calculate the second value from the first, but this will take some more processor time instead.
For my research, I found & adapted a fairly basic, but relatively efficient, Segmented sieve of Eratosthenes. Although it is fairly good as it is, I made it more efficient by replacing C++ vectors with C type fixed arrays, using bits to store certain values instead of bytes (to help with the memory cache issue), etc. Nonetheless, note that the PrimeSieve library which this originally came from is now much more efficient, but I didn't use it for various reasons of adaptability, complete confidence in understanding it, easy distribution of it, etc., with the segmented sieve being efficient enough (especially after my enhancements) for my purposes.
As for your side question, I have not checked into it to any extent, but I believe it would be possible to derive other modulo type checks.
Good luck with your investigations into methods to generate prime numbers. I hope that you someday find an improvement to the state of art methods.
answered Dec 31 '18 at 20:32
John OmielanJohn Omielan
4,1962215
$endgroup$
$begingroup$
Thank you for this comprehensive answer and your kind words. Although I doubt to find an improvement to the state of the art anytime I enjoy wasting my time with primes
$endgroup$
– g3nuine
Jan 3 at 0:35
add a comment |
$begingroup$
You have an interesting idea. However, regarding your question about it being efficient, if you mean compared to the current state of the art prime generating algorithms, then I believe the answer is unfortunately no. Note I am not an expert myself regarding the various algorithms used for generating primes, but I'm currently doing some prime research so I have investigated what method might work best for me, and have implemented plus optimized a basic solution, so I have some knowledge about this area.
Note your formula to determine composites uses up to $2$ modulus calculations to check whether or not a value is a multiple of each prime. This could be made somewhat more efficient by just getting the integer remainder and then using it to do the $2$ comparisons. However, modulus operations are not particularly efficient apart from using certain constants that a good optimizing compiler will do more efficiently in certain cases (e.g., a bit shift for a power of 2). Instead, according to Optimizing software in C++, in section 14.5 Integer Division, it says "Integer division takes much longer time than addition, subtraction and multiplication (27 - 80 clock cycles for 32 - bit integers, depending on the processor)".
As for reducing the number of values to check, among the odd integers, using just $6k pm 1$ means you are only bypassing the ones of the form $6k + 3$, so you are checking $frac{2}{3}$ of them. However, with various Wheel factorization methods, you can get a considerably better reduction in the number of values to check, so at least some of the fastest prime generation algorithms use this.
Another important issue, especially for modern computers, that many people are not aware of is the degree that the amount of memory your program is actively using compared to how much & how fast your memory cache can affect the overall speed. Although processor speeds have improved considerably, at least up until a few years ago, memory speeds have not improved as much since about $10$ or $15$ years ago, so the memory cache has become a more important issue. In fact, due to the nature of what I'm doing, I estimate that it affects around $70$ or $80$ percent of my program speed. With your algorithm, you could store all of the $b_n$ values in memory, which would use more of the memory cache, or just calculate the second value from the first, but this will take some more processor time instead.
For my research, I found & adapted a fairly basic, but relatively efficient, Segmented sieve of Eratosthenes. Although it is fairly good as it is, I made it more efficient by replacing C++ vectors with C type fixed arrays, using bits to store certain values instead of bytes (to help with the memory cache issue), etc. Nonetheless, note that the PrimeSieve library which this originally came from is now much more efficient, but I didn't use it for various reasons of adaptability, complete confidence in understanding it, easy distribution of it, etc., with the segmented sieve being efficient enough (especially after my enhancements) for my purposes.
As for your side question, I have not checked into it to any extent, but I believe it would be possible to derive other modulo type checks.
Good luck with your investigations into methods to generate prime numbers. I hope that you someday find an improvement to the state of art methods.
answered Dec 31 '18 at 20:32
John OmielanJohn Omielan
4,1962215
$endgroup$
$begingroup$
Thank you for this comprehensive answer and your kind words. Although I doubt to find an improvement to the state of the art anytime I enjoy wasting my time with primes
$endgroup$
– g3nuine
Jan 3 at 0:35
add a comment |
$begingroup$
You have an interesting idea. However, regarding your question about it being efficient, if you mean compared to the current state of the art prime generating algorithms, then I believe the answer is unfortunately no. Note I am not an expert myself regarding the various algorithms used for generating primes, but I'm currently doing some prime research so I have investigated what method might work best for me, and have implemented plus optimized a basic solution, so I have some knowledge about this area.
Note your formula to determine composites uses up to $2$ modulus calculations to check whether or not a value is a multiple of each prime. This could be made somewhat more efficient by just getting the integer remainder and then using it to do the $2$ comparisons. However, modulus operations are not particularly efficient apart from using certain constants that a good optimizing compiler will do more efficiently in certain cases (e.g., a bit shift for a power of 2). Instead, according to Optimizing software in C++, in section 14.5 Integer Division, it says "Integer division takes much longer time than addition, subtraction and multiplication (27 - 80 clock cycles for 32 - bit integers, depending on the processor)".
As for reducing the number of values to check, among the odd integers, using just $6k pm 1$ means you are only bypassing the ones of the form $6k + 3$, so you are checking $frac{2}{3}$ of them. However, with various Wheel factorization methods, you can get a considerably better reduction in the number of values to check, so at least some of the fastest prime generation algorithms use this.
Another important issue, especially for modern computers, that many people are not aware of is the degree that the amount of memory your program is actively using compared to how much & how fast your memory cache can affect the overall speed. Although processor speeds have improved considerably, at least up until a few years ago, memory speeds have not improved as much since about $10$ or $15$ years ago, so the memory cache has become a more important issue. In fact, due to the nature of what I'm doing, I estimate that it affects around $70$ or $80$ percent of my program speed. With your algorithm, you could store all of the $b_n$ values in memory, which would use more of the memory cache, or just calculate the second value from the first, but this will take some more processor time instead.
For my research, I found & adapted a fairly basic, but relatively efficient, Segmented sieve of Eratosthenes. Although it is fairly good as it is, I made it more efficient by replacing C++ vectors with C type fixed arrays, using bits to store certain values instead of bytes (to help with the memory cache issue), etc. Nonetheless, note that the PrimeSieve library which this originally came from is now much more efficient, but I didn't use it for various reasons of adaptability, complete confidence in understanding it, easy distribution of it, etc., with the segmented sieve being efficient enough (especially after my enhancements) for my purposes.
As for your side question, I have not checked into it to any extent, but I believe it would be possible to derive other modulo type checks.
Good luck with your investigations into methods to generate prime numbers. I hope that you someday find an improvement to the state of art methods.
answered Dec 31 '18 at 20:32
John OmielanJohn Omielan
4,1962215
$endgroup$
You have an interesting idea. However, regarding your question about it being efficient, if you mean compared to the current state of the art prime generating algorithms, then I believe the answer is unfortunately no. Note I am not an expert myself regarding the various algorithms used for generating primes, but I'm currently doing some prime research so I have investigated what method might work best for me, and have implemented plus optimized a basic solution, so I have some knowledge about this area.
Note your formula to determine composites uses up to $2$ modulus calculations to check whether or not a value is a multiple of each prime. This could be made somewhat more efficient by just getting the integer remainder and then using it to do the $2$ comparisons. However, modulus operations are not particularly efficient apart from using certain constants that a good optimizing compiler will do more efficiently in certain cases (e.g., a bit shift for a power of 2). Instead, according to Optimizing software in C++, in section 14.5 Integer Division, it says "Integer division takes much longer time than addition, subtraction and multiplication (27 - 80 clock cycles for 32 - bit integers, depending on the processor)".
As for reducing the number of values to check, among the odd integers, using just $6k pm 1$ means you are only bypassing the ones of the form $6k + 3$, so you are checking $frac{2}{3}$ of them. However, with various Wheel factorization methods, you can get a considerably better reduction in the number of values to check, so at least some of the fastest prime generation algorithms use this.
Another important issue, especially for modern computers, that many people are not aware of is the degree that the amount of memory your program is actively using compared to how much & how fast your memory cache can affect the overall speed. Although processor speeds have improved considerably, at least up until a few years ago, memory speeds have not improved as much since about $10$ or $15$ years ago, so the memory cache has become a more important issue. In fact, due to the nature of what I'm doing, I estimate that it affects around $70$ or $80$ percent of my program speed. With your algorithm, you could store all of the $b_n$ values in memory, which would use more of the memory cache, or just calculate the second value from the first, but this will take some more processor time instead.
For my research, I found & adapted a fairly basic, but relatively efficient, Segmented sieve of Eratosthenes. Although it is fairly good as it is, I made it more efficient by replacing C++ vectors with C type fixed arrays, using bits to store certain values instead of bytes (to help with the memory cache issue), etc. Nonetheless, note that the PrimeSieve library which this originally came from is now much more efficient, but I didn't use it for various reasons of adaptability, complete confidence in understanding it, easy distribution of it, etc., with the segmented sieve being efficient enough (especially after my enhancements) for my purposes.
As for your side question, I have not checked into it to any extent, but I believe it would be possible to derive other modulo type checks.
Good luck with your investigations into methods to generate prime numbers. I hope that you someday find an improvement to the state of art methods.
answered Dec 31 '18 at 20:32
John OmielanJohn Omielan
4,1962215
answered Dec 31 '18 at 20:32
John OmielanJohn Omielan
4,1962215
answered Dec 31 '18 at 20:32
John OmielanJohn Omielan
4,1962215
answered Dec 31 '18 at 20:32
John OmielanJohn Omielan
4,1962215
4,1962215
$begingroup$
Thank you for this comprehensive answer and your kind words. Although I doubt to find an improvement to the state of the art anytime I enjoy wasting my time with primes
$endgroup$
– g3nuine
Jan 3 at 0:35
add a comment |
$begingroup$
Thank you for this comprehensive answer and your kind words. Although I doubt to find an improvement to the state of the art anytime I enjoy wasting my time with primes
$endgroup$
– g3nuine
Jan 3 at 0:35
$begingroup$
Thank you for this comprehensive answer and your kind words. Although I doubt to find an improvement to the state of the art anytime I enjoy wasting my time with primes
$endgroup$
– g3nuine
Jan 3 at 0:35
$begingroup$
Thank you for this comprehensive answer and your kind words. Although I doubt to find an improvement to the state of the art anytime I enjoy wasting my time with primes
$endgroup$
– g3nuine
Jan 3 at 0:35
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%2f3057813%2fis-this-an-efficient-type-of-sieve%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$
What is the point of your $p$, $q$, $r$ functions? You don't seem to be using those particular expressions for anything and it would be vastly simpler just to say that $f(n)$ is the $n$th number of the form $6kpm 1$.
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:43
1
$begingroup$
(Or, if you insist of having an arithmetic-looking formula for some reason, $f(n)=3n+3/2-(-1)^n/2$).
$endgroup$
– Henning Makholm
Dec 31 '18 at 15:47
$begingroup$
Yes thats way better thanks
$endgroup$
– g3nuine
Dec 31 '18 at 15:51