Sieb des Eratosthenes

[codie]

Hi

Ich soll ein Programm für den Algorithmus des Sieb des Eratosthenes implementieren und dann alle Primzahlen bis zur Grenze ausgeben.
Ich hab bereits den Teil zur Prüfung ob Primzahl oder nicht, der funktioniert auch, aber die Ausgabe macht mir Probleme. Ich kann zwar das Array mit 0 und 1 ausgeben für true / false ausgeben, aber nicht die richtigen Zahlenwerte dafür.

Die Ausgabefunktion funltioniert nicht, da kommen die Fehlermeldungen:

Zeile 36: cannot convert 'bool' to 'bool*' for argument '1' to 'void print (bool*, bool*)'
Zeile 44: ISO C++ forbids comparison between pointer and integer [-fpermissive]

Ich bin langsam echt am verzweifeln
BTW: ich bin ziemlicher Anfänger mit Zeiger

Hier erstmal der Code:

#include <iostream>

using namespace std;

void print(bool *AnfangArray, bool *EndeArray);

int main()
{
    int size;
    int i,j;

    cout <<"Grenze eingeben: " << endl;
    cin >> size;

    bool *a = new bool [size+1];

    for (i=0; i <= size+1; i++){
        a[i] = i;
    }

    a[0] = false;
    a[1] = false;

    for(i = 2; i < size; i++){
            a[i] = false;
    }

    for(i = 2; i < size/2; i++){
        for(j = 2; j < size/2 ; j++){
            if(i*j < size)
                a[i*j] = true;
        }
    }

    print(a[0], a[size+1]);

    return 0;
}

void print(bool *AnfangArray, bool *EndeArray){ //AnfangArray zeigt auf erstes Element von a,
                                                //EndeArray zeigt auf Element hinter des letzten Elements von a
   for (*AnfangArray; *EndeArray; AnfangArray++ ) {
        if (AnfangArray == 1){                  //wenn Element true ist, Primzahl ausgeben
            cout << AnfangArray << endl;
        }
   }

}

Ich hoffe, ihr könnt mir helfen

[Skym0sh0]

#include <iostream>

using namespace std;

void print(bool *AnfangArray, bool *EndeArray);

int main()
{
    int size;
    int i,j;

    cout <<"Grenze eingeben: " << endl;
    cin >> size;

	// Wieso +1?
    bool *a = new bool [size+1];

    for (i=0; i <= size+1; i++){
        a[i] = i;
    }

    a[0] = false;
    a[1] = false;

    for(i = 2; i < size; i++){
            a[i] = false;
    }

    for(i = 2; i < size/2; i++){
        for(j = 2; j < size/2 ; j++){
            if(i*j < size)
                a[i*j] = true;
        }
    }

	// Du willst hier einen Zeiger auf den Anfang und einen auf das Ende des Arrays übergeben? Dann mach das doch
	// mit print(a, a+size+1);
    print(a[0], a[size+1]);

	// Hier fehlt ein delete[] a;
    return 0;
}

void print(bool *AnfangArray, bool *EndeArray){ //AnfangArray zeigt auf erstes Element von a,
                                                //EndeArray zeigt auf Element hinter des letzten Elements von a
	// Diese Schleifenbedingungen und alles drum herum sieht sehr falsch aus
   for (*AnfangArray; *EndeArray; AnfangArray++ ) {
        if (AnfangArray == 1){                  //wenn Element true ist, Primzahl ausgeben
            cout << AnfangArray << endl;
        }
   }
}

Dadrüber hinaus stellt sich mir die Frage: wieso nutzt du keinen std::vector?

[manni66]

Welchen Sinn hat das:

for (i=0; i <= size+1; i++){ 
        a[i] = i; 
    }

Außerdem läuft die Schleife um 1 zu weit.

[codie]

Danke für die bisherigen Hinweise

std::vector kenn ich leider nicht, ich programmier noch nicht sehr lange.
ja die Ausgabefunktion ist mehr oder weniger Pseudocode. Ich das versucht hab richtig zu programmieren, aber ich kann das nicht, da ich eben nicht weiß wie ich die Pointer mit boolean vergleichen kann.

Und die Schleife hab ich vergessen wieder rauszulöschen, hab ich übersehen

[manni66]

Du willst keinen Pointer mit boolean vergleichen. Du willst dereferenziern. Und du willst "den nächsten Wert": +1.

Wenn du mit Pointern arbeiten willst, musst du halt auch lernen, wie man damit umgeht.

[Flodul]

Hier, das ist eine C++20-Lösung die in Sachen Performance unschlagbar ist:

#include <iostream>
#include <vector>
#include <charconv>
#include <string_view>
#include <algorithm>
#include <fstream>
#include <cctype>
#include <cstring>
#include <bit>
#include <cmath>

#if defined(_MSC_VER)
	#pragma warning(disable: 26495) // uninitialized member
#endif
#if defined(__llvm__)
	#pragma clang diagnostic ignored "-Wdangling-else"
#endif

using namespace std;

int main( int argc, char **argv )
{
	constexpr size_t BUF_SIZE = 0x100000;
	try
	{
		size_t end;
		if( argc < 2 )
			return EXIT_FAILURE;
		char const *sizeStr = argv[1];
		bool hex = sizeStr[0] == '0' && (sizeStr[1] == 'x' || sizeStr[1] == 'X');
		sizeStr += 2 * hex;
		if( from_chars_result fcr = from_chars( sizeStr, sizeStr + strlen( sizeStr ), end, !hex ? 10 : 16 ); (bool)fcr.ec || *fcr.ptr )
			return EXIT_FAILURE;
		if( !++end )
			throw bad_alloc();
		using word_t = size_t;
		constexpr size_t BITS = sizeof(word_t) * 8;
		size_t bEnd = (end + BITS - 1) & -(ptrdiff_t)BITS;
		if( bEnd < end )
			throw bad_alloc();
		union ndi_word_t { word_t w; ndi_word_t( word_t w ) : w( w ) {}	};
		using bit_vec = vector<ndi_word_t>;
		using bit_it = bit_vec::iterator;
		bit_vec sieve( (end + BITS - 1) / BITS, (word_t)0xAAAAAAAAAAAAAAAAu );
		ofstream ofs;
		union ndi_t { char c; ndi_t() {} };
		using ndi_vec = vector<ndi_t>;
		constexpr size_t AHEAD = 32;
		ndi_vec printBuf;
		ndi_vec::iterator bufBegin, bufEnd, bufFlush;
		if( argc < 3 || *argv[2] )
		{
			ofs.exceptions( ofstream::failbit | ofstream::badbit );
			ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::trunc );
			printBuf.resize( BUF_SIZE + AHEAD - 1 );
			bufBegin = printBuf.begin();
			bufEnd = bufBegin;
			bufFlush = bufBegin + BUF_SIZE;
		}
		auto print = [&]() { ofs << string_view( &to_address( bufBegin )->c, &to_address( bufEnd )->c ); };
		bit_it const pSieveEnd = sieve.end();
		size_t sqr = (ptrdiff_t)ceil( sqrt( (ptrdiff_t)end ) );
		for( size_t p = 2; p < end; )
		{
			if( ofs.is_open() )
			{
				auto [ptr, ec] = to_chars( &bufEnd->c, &to_address( bufEnd + (AHEAD - 1) )->c, p );
				if( (bool)ec ) [[unlikely]]
					throw system_error( (int)ec, generic_category(), "converson failed" );
				bufEnd = ptr - &bufBegin->c + bufBegin; // NOP
				bufEnd++->c = '\n';
				if( bufEnd >= bufFlush )
					print(),
					bufEnd = bufBegin;
			}
			if( ++p == end ) [[unlikely]]
				break;
			for( bit_it pSieve = sieve.begin() + p / BITS; ; )
			{
				size_t g = countr_zero( (word_t)(pSieve->w & (word_t)-1 << p % BITS) );
				p = (p & -(ptrdiff_t)BITS) + g;
				if( g != BITS )
					break;
				if( ++pSieve == pSieveEnd )
					goto end;
			}
			bit_it pSieve = sieve.begin();
			if( p < sqr )
			{
				size_t m = p * p;
				word_t mask = rotl( (word_t)-2, m % BITS );
				if( p >= BITS ) [[likely]]
					do
						pSieve[m / BITS].w &= mask,
						mask = rotl( mask, (int)p % BITS ),
						m += p;
					while( m < end );
				else
				{
					pSieve += m / BITS;
					do
					{
						word_t punch = -1, oldMask;
						do
							punch &= mask,
							oldMask = mask,
							mask = rotl( mask, (int)p );
						while( mask < oldMask );
						pSieve->w &= punch;
					} while( ++pSieve != pSieveEnd );
				}
			}
		}
	end:
		if( ofs.is_open() )
			print();
		return EXIT_SUCCESS;
	}
	catch( bad_alloc const & )
	{
		cout << "out of memory" << endl;
	}
	catch( ios_base::failure const & )
	{
		cout << "I/O error" << endl;
	}
	catch( system_error const &se )
	{
		cout << se.what() << endl;
	}
}

[SeppJ]

Ob das noch jemanden was bringt nach 8 Jahren? Wenn du deinen Code diskutiert haben möchtest, dann mach lieber einen neuen Thread auf. Mir macht es jedenfalls Angst, wenn dein Code erst einmal die meiste Zeit damit beschäftigt ist, selber Zahlen aus Strings zu extrahieren, danach hatte ich keine Lust, weiterzulesen.