Re: OT: Re: Sieve of Erastosthenes optimized to the max

Am 19.08.2024 um 22:34 schrieb Vir Campestris:

On 16/08/2024 18:35, Bonita Montero wrote:

But basically I don't think it is a good idea to skip numbers exept
multiples of two. With the three you save a sixth of memory, with
the five you save a 15-th and at the end you get about 20% less
storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...)
for a lot of computation. That's the point where I dropped this
idea and I think this extra computation is higher than the time
for the saved memory loads.

 BTW I was just checking outputs.
      66049
     67591
     69133
     69647
     71189
     72217
     72731
     75301
     78899
     79927
     80441
     81469
     85067
     86609
     89179
     89693
     90721
     92263
     94319
     95861
     97403
     98431
     99973
 all show in the output for your program, but not mine. I think you'll find they are products of 257 and the next few primes.
 Andy

I wrote a small program to look if the above numbers are included in my
output:
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
int main( int argc, char **argv )
{
if( argc < 3 )
return EXIT_FAILURE;
auto read = []( char const *file, vector<size_t> &vec )
{
ifstream ifs( file );
while( !ifs.eof() )
{
size_t number;
ifs >> number;
vec.emplace_back( number );
}
sort( vec.begin(), vec.end() );
};
vector<size_t> large, small;
read( argv[1], large );
read( argv[2], small );
for( size_t lookup : small )
{
auto where = lower_bound( large.begin (), large.end(), lookup );
if( where == large.end() || *where != lookup )
continue;
cout << lookup << endl;
}
}
None of the numbers are my output.