20200912, 05:47  #1 
Aug 2020
2×3×5 Posts 
General question about sieving software
I'm not sure if this is the proper section, but anyway.
Sieve of Eratosthenes takes a prime, marks all multiples of it, then moves to the next unmarked number and so on. But when I view the output of sieving software such as sr2sieve it appears like each prime has at max one number it factors. In factors.txt no prime turns up more than once. It seems like sieving stops as soon as one multiple of that prime is found. So what if that particular prime is a factor of more than one candidate in the sieve file? Especially for small primes such as 2 or 3 this will happen a lot and I'm sure it's taken care of, but how? Last fiddled with by bur on 20200912 at 05:48 
20200912, 07:49  #2 
Romulan Interpreter
Jun 2011
Thailand
8873_{10} Posts 
If you sieve for n to 1 million, you have one million candidates, but you sieve with primes much larger. Take a range of 1 million consecutive numbers. Small primes (below 1 million) are sieved out so fast that you can't see them (not really, but you got the idea, see below). For the larger primes, most of them will divide no candidate from the million consecutive numbers, as their "step" (say, in Eratosthenes' sieve) is larger then a million, they will completely "jump over" your interval. Few primes will "step" into your interval, but only once, as their "step" is larger than a million, next step is outside. Does this makes sense?
Showing all "small primes" stuff is not wanted, because it is bloody time consuming (printing on screen or saving in a file). But you can do it, if you want. For srsieve and relatives, there is a parameter (maybe m ?? you have to check, my memory is weaker and weaker) which says "do not show factored candidates for primes lower than this value", which is by default (if not specified), set to 1 million (again, please double check this). You can use "m 2" or "m 11" to see all candidates eliminated when sieving with primes larger than 2, respectively larger than 11 (for example). In the first case, you will see an endless stream of candidates eliminated by the prime 3 (all numbers in your range which are divisible by 3). Last fiddled with by LaurV on 20200912 at 07:50 
20200912, 08:22  #3 
"Curtis"
Feb 2005
Riverside, CA
3^{3}·163 Posts 
newpgen also does not print the candidates factored out by small primes, but when one fires it up on a new sieve it'll give a status line for each prime. So, you'll be able to see just how many candidates are divisible by 5.
srsieve is faster than newpgen, so one would run the older software only for this curiosity (or for other forms for which newpgen works but sr[x]sieve doesn't). 
20200913, 16:32  #4  
Aug 2020
2·3·5 Posts 
Quote:
Say my primes are of magnitude 1E12 and candidates are k * 2^1E6 + 1. Then any of the primes can easily factor various candidates. For example 1E12 * 1E100 is 1E125 which is still much smaller than my candidates which are on the magnitude of 1E1000000. But since I will probably not sieve up to 1E125 I will not find that composite number. That all those composites are not printed to screen, I get that. But the factors.txt also doesn't contain more than one composite per prime. And that also applies to relatively small primes around 1E5. Last fiddled with by bur on 20200913 at 16:36 

20200914, 06:40  #5 
"Curtis"
Feb 2005
Riverside, CA
10461_{8} Posts 
I don't think it applies to evensmaller primes than 1e5 small primes should divide many candidates.
By the time you're sieving out a prime near 100,000, I think there are fewer than 100k candidates left in your sieve, and it's merely unlikely for one to divide more than one candidate; however, if it was a random occurence, it *should* happen once in a while. Can you set a sieve to record factors from 10,000 to 100,000 and see if you find instances of one prime factoring multiple candidates? or 1,000 to 2,000? Maybe it's just so rare at large values that you haven't seen it yet. 
20200914, 08:13  #6 
Aug 2020
2·3·5 Posts 
The thing is, what does happen is that a single candidate is factored by more than one prime in a relatively small range.
The sieve file contains 65000 candidates and I was sieving in four seperate instances in ranges like 20E1125E11, 25E11 to 30E11 and so on. Almost always the sr2sieve.exe with higher range reported, e.g. 400 found factors and only 375 got removed by srfile because the remaining 25 were already removed in the 20E1125E11 factors.txt. Of course having one candidate being factored by several primes if different from one prime factoring several candidates. Still, I'd like to know how this is handled. Is certain that a prime is only considered until one factoring candidate was found? Especially for primes around 100,000 this seems inefficient as I would think one prime factors more than one candidate in the sieve. Maybe it's not worth the effort though. Last fiddled with by bur on 20200914 at 08:13 
20200929, 17:10  #7 
Aug 2020
11110_{2} Posts 
For the record, common sieving software DOES check all candidates in the sieve against a prime factor. The reason why you almost never see a prime dividing more than one candidate is simply that the chances are so low.
For example, my current sieving with P ~ 1E12 yields one factor in about 1E10 primes. So the probability that one prime divides two candidates is around 1E20. What I still don't understand is, why it apparently happens often that a candidate is divided by more than one prime in a relatively small range of say 10E12 to 11E12. I think that's strange, because the fact that the candidate is still in the sieve means it didn't have any prime factor for 2 < p < 10E12. But it has two in that aforementioned range. Could be conincidence, but it happened frequently for a sieve with about 75000 candidates. At least I assume that happens since when I run four sr2sieve instances simultaneously on the same abcd file and afterwards remove the factors srfile frequently removes 1 less candidate then the respective sr2sieve reported factors. So I assumed the candidate was already removed by another factor. Last fiddled with by bur on 20200929 at 17:10 
20200930, 03:32  #8 
Romulan Interpreter
Jun 2011
Thailand
8873_{10} Posts 
So what? Take a million odd numbers. Or a million numbers of the form n^2+1. They are not consecutive, but from sieving point of view, they are. When you sieve them with the prime 3, you still count (by some algorithm, in case of consecutive n, once you figure out how/where to start), one, two, three, cut it out, one, two, three, cut it out, one, two, three, cut it out, one, two, three, cut it out. Think about it.

20201003, 06:01  #9 
Aug 2020
1E_{16} Posts 
Sorry, but I still don't get it. Using 2^n + 1 for the first 10 values we get:
3 5 9 17 33 65 129 257 513 1025 5 divides the 2nd, 6th and 10th candidate. So it divides not at most every 5th number, but more. The same should apply to much larger prime factors. 
20201003, 13:35  #10  
"Alexander"
Nov 2008
The Alamo City
390_{10} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
General factoring algorithms not using sieving  mickfrancis  Factoring  21  20160222 19:38 
S9 and general sieving discussion  Lennart  Conjectures 'R Us  31  20140914 15:14 
What about general purpose sieving of k*b^n+/1?  jasong  GPU Computing  1  20120403 10:52 
new sieving software  Thomas11  Riesel Prime Search  81  20111105 19:16 
Sieving Software  lavalamp  Software  10  20071020 23:07 