Keskustelu: Ohjelmointikysymykset: C++: Alkulukuetsijä

//Alkulukujen etsijä
//Tämän ohjelman tarkoitus on etsiä alkuluvut, jotka löytyvät halutulta väliltä.
//Toivoisin kuitenkin, että et sijoita lukujen kohdille liian isoa numeroa, silloin toimivuutta ei ole taattu.
//Alkuluvuksi luokitellan luku, joka on jaollinen vain itsellään ja yhdellä.
#include <stdio.h>

//Määritykset:
#define	LUKU_MIN	0	//Minimi luku miltä väliltä alkulukuja etsitään.
#define	LUKU_MAX	100	//Maksimi luku miltä väliltä alkulukuja etsitään.
#define	RIVI_MAX	5	//Montako lukua per rivi.
#define	ALKUVUT_MAX	200	//Mahdollistaa 201 alkuluvun tallentamisen.

main()
{
//JUMP_MODE:a tarvitaan jos LUKU_MIN > 0, jotta ohjelma ei tulostaisi ei haluttuja alkulukuja.
	char JUMP_MODE = 0, ALKULUKU = 1;

//alkuluvut[200] mahdollistaa vain 201 alkuluvun tallentamisen.
	int x = 0, y = 0, luku = 2, rivi = 0, alkuluvut[ALKUVUT_MAX];

//Määritetään ensimmäinen alkuluku turhan koodin välttämiseksi ja tehdään se tällä tyylillä selveyden vuoksi.
	alkuluvut[0] = 2;

//Poikkeuksena täytyy printata 2 jotta vältytään ylimääräiseltä koodilta
	if(LUKU_MIN <= 2)	{
		printf("%5d", 2);
		++rivi;
	}

//Etsitään alkulukuja
	for(; luku <= LUKU_MAX; ++luku)	{
//Jos luku on jaettavissa joillakin edellisitä alkuluvuista, luku ei ole alkuluku.
		for(; y >= 0; --y)	{
			if(luku % alkuluvut[y] == 0)	{
				ALKULUKU = 0;
				break;
			}
		}

//Tämän käydessä toteen luku on alkuluku.
			if(ALKULUKU == 1)	{
				++x;
				if(luku < LUKU_MIN)	{
					alkuluvut[x] = luku;
					JUMP_MODE = 1;	//Asetetaan hyppytila tulostuksen ohitusta varten.
				}
				if(JUMP_MODE != 1)	{
					alkuluvut[x] = luku;
					printf("%5d", luku);
					++rivi;

				if(rivi >= RIVI_MAX)	{
					printf("\n");
					rivi = 0;
					}
				}
			}
			y = x;
		if(JUMP_MODE == 1)
			JUMP_MODE = 0;

		if(ALKULUKU == 0)
			ALKULUKU = 1;

		if(y >= ALKUVUT_MAX)	{
			printf("\nNo nyt loppui tallennustila alkuluvuille");
			return 0;
		}
	}
}

int Alkuluvut(int Max_Lukuja, int * Lukutaulu, int Max_Luku = 0x7fffffff)
{
    int a, Luku, Lisays, Viimeinen, Lukuja;

    // Max_Lukuja ei voi olla suurempi kuin Max_Luku
    if (Max_Lukuja > Max_Luku)
        Max_Lukuja = Max_Luku;

    // Ettei se ole liian pieni...
    if (Max_Lukuja < 1) return 0;
    Lukutaulu[0] = 2;
    if (Max_Lukuja < 2) return 1;
    Lukutaulu[1] = 3;
    if (Max_Lukuja < 2) return 2;

    // Kaksi lukua valmiina (2 ja 3)
    Lukuja = 2;
    Lisays = 2;
    Viimeinen = 0;
    Luku = 5;

    while (Lukuja < Max_Lukuja && Luku < Max_Luku)
    {
        // Jakotesti vain neliöjuureen asti
        while (Lukutaulu[Viimeinen] * Lukutaulu[Viimeinen] <= Luku)
            Viimeinen++;

        // Jakotestit (kakkosta ei tarvita)
        for (a = 1; a < Viimeinen; a++)
        {
            if (Luku % Lukutaulu[a] == 0)
            {
                a = -1;
                break;
            }
        }

        // a == -1, jos tuli break
        if (a != -1)
        {
            Lukutaulu[Lukuja] = Luku;
            Lukuja++;
        }

        // Lisätään ja muutetaan lisäystä
        Luku += Lisays;
        Lisays ^= (4 | 2);
    }

    return Lukuja;
}

// Esimerkki
int Luvut[100];
int Alkulukuja = Alkuluvut(100, Luvut);

#include <iostream>
using namespace std;

int main(int arg, char *argv[]) {

	long long int lukuja;
	if (arg>1) {
		lukuja=atoi(argv[1]);
	} else {
		cout << "Kuinka pitkälle lasketaan?\n";
		cin >> lukuja;
	}

	bool *luku=new bool[lukuja]; //true = ei ole alkuluku, false=alkuluku
	long long int i;
	cout << "\nMuistia kuluu " << sizeof(luku)*lukuja << " tavua ( " << (sizeof(luku)*lukuja)/1024 << " kt) \n\n";
	//alustetaan
	for (i=0; i<lukuja; i++)
		luku[i]=false;

	for (i=2; i<=lukuja; i++) {
		//onko i jo merkitty ei_alkuluvuksi
		if (luku[i]==false) {
			//lukujonon kaikki i:llä jaolliset luvut paitsi i merkataan
			for (long long int n=2*i; n<lukuja; n+=i)
				luku[n]=true;
		}
	}


	char vastaus;
	if (arg==1) {
		cout << "\nHaluatko nähdä alkuluvut k/e?\n";
		vastaus; cin >> vastaus;
	}
	if (vastaus=='k') {
		cout << "Löydettiin seuraavat alkuluvut: \n";
		for (i=2; i<lukuja; i++) {
			if (luku[i]==false){
				cout << i << "\n";
			}
		}
	}


	delete[] luku;
	luku=0;

	return 0;
}