Tiny programs (C, C++, C#, ...)

/*
 * Soubor: prvocisl.c - Eratostenovo sito (modul se linkuje zvlast)
 * Kamil Dudka, FIT, DU1, priklad a), 1.4.2005
 */
 
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include "error.h"	// Rozhrani modulu error.c (obsluha chyby)
 
 
// Definuje pocet bitu jedne alokacni jednotky bitoveho pole
#define BA_UNITBITS		(8*sizeof(unsigned int))
 
// Vraci pocet jednotek, ktere je treba alokovat pro dany pocet bitu
#define BA_UNITCOUNT(size)	((size)/BA_UNITBITS+((size)%BA_UNITBITS!=0))
 
// Na zaklade indexu vraci cislo jednotky bitoveho pole
#define BA_UNIT(index)		((index)/BA_UNITBITS)
 
// Na zaklade indexu vraci offset v ramci jedne alokacni jednotky bitoveho pole
#define BA_BIT(index)		((index)%BA_UNITBITS)
 
// Makro, ktere definuje a inicializuje bitove pole
#define BitArray(jmeno_pole,velikost) \
	const size_t jmeno_pole##_size = (velikost); \
	unsigned int jmeno_pole [BA_UNITCOUNT(velikost)] = {0};
 
 
#ifdef USE_INLINE
	// Pokud je definovano makro USE_INLINE pouziji se inline funkce
	// Jako posledni parametr se predeva velikost pole pro kontorlu rozsahu
#	define SetBit(jmeno_pole,index,vyraz) \
		inlineSetBit(jmeno_pole,index,vyraz,jmeno_pole##_size)
#	define GetBit(jmeno_pole,index) \
		inlineGetBit(jmeno_pole,index,jmeno_pole##_size)
 
	// Prototypy inline funkci
	// Pokud neni definovano makro USE_INLINE, nejsou definovany prototypy.
	// Nedefinovani prototypu zajisti, ze funkce nebudou pouzity tim,
	// ze prekladac generuje chybu (nebo warovani).
	inline void inlineSetBit(unsigned int *, unsigned long, bool, size_t);
	inline bool inlineGetBit(unsigned int *, unsigned long, size_t);
 
 
#else
	// Pokud neni definovano makro USE_INLINE pouziji se klasicka makra
 
	// Makro, ktere nastavy zadany bit zadaneho pole na hodnotu zadaneho vyrazu
#	define SetBit(jmeno_pole,index,vyraz) \
		do { \
			if ((index)>=jmeno_pole##_size) \
				Error ("Index %i mimo rozsah 0..%d",(index),(jmeno_pole##_size-1)); \
			jmeno_pole [BA_UNIT(index)] = (vyraz) ? \
			jmeno_pole [BA_UNIT(index)] | (1<<BA_BIT(index)) : \
			jmeno_pole [BA_UNIT(index)] & (~(1<<BA_BIT(index))); \
		} while (0)
 
	// Makro, ktere vraci hodnotu zadaneho bitu zadaneho pole
#	define GetBit(jmeno_pole,index) \
		( ((index)>=jmeno_pole##_size) ? \
		(Error ("Index %i mimo rozsah 0..%d",(index),(jmeno_pole##_size-1)), 0) : \
		(0!=( jmeno_pole [BA_UNIT(index)] & (1<<BA_BIT(index)) )) )
#endif
 
#define N	15000000L
 
/*
 * Algoritmus Eratostenova sita je implementovan primo ve funkci main().
 * Pro prehlednost jsem pouzil stejne identifikatory jako v zadani ulohy.
 */
int main (void)
{
	// Vypocet odmocninu z poctu prvku eratostenova sita
	const unsigned long SqrtN = (unsigned long) sqrt (N);
 
	unsigned long i,n;
 
	// Definice a inicializace bitoveho pole o N+1 prvcich
	BitArray(p, N+1);
 
	// Vlastni cyklus Eratostenova sita
	for (i=2; i<=SqrtN; i++) {
 
		// Najde prvni nulovy bit - prvocislo
		for (; i<=N && 0!= GetBit(p,i); i++);
 
		// Vsechny jeho nasobky nejsou prvocisla
		for (n=i<<1; n<=N; n+=i)
			SetBit(p,n,1);
	}
 
	// Napocita deset prvocisel od konce
	for (n=0, i=N; n<10; n++, i--)
		for (; 0!=GetBit(p,i); i--);
 
	// Vypise prvocisla v vzestupnem poradi
	for (n=0; n<10; n++, i++) {
		for (; i<N && 0!=GetBit(p,i); i++);
		printf ("%lu\n",i);
	}
 
	return 0;
}
 
// Inline funkce nahrazujici makro SetBit()
inline void inlineSetBit(unsigned int *array, unsigned long index, bool expr, size_t size) {
	if (index>=size)
		// Index mimo rozsah - obsluha chyby
		Error ("Index %i mimo rozsah 0..%d",(index),(size-1));
 
	if (expr)
		// Nastaveni pozadovaneho bitu bitoveho pole
		array [index/BA_UNITBITS] |= 1 << (index % BA_UNITBITS);
	else
		// Vynulovani pozadovaneho bitu bitoveho pole
		array [index/BA_UNITBITS] &= ~(1 << (index % BA_UNITBITS));
}
 
// Inline funkce nahrazujici makro GetBit()
inline bool inlineGetBit(unsigned int *array, unsigned long index, size_t size) {
	if (index>=size)
		// Index mimo rozsah - obsluha chyby
		Error ("Index %i mimo rozsah 0..%d",(index),(size-1));
 
		// Vyraz je ekvivalentni se stejnojmennym makrem
	return (0!= (array [index/BA_UNITBITS] & (1<< (index % BA_UNITBITS))));
}