/*
* 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))));
}