Computer programming - Homework 7

1. Write a function that prints all primes up to a value given as a parameter, using the sieve of Eratosthenes.
a) For a first simple solution use an array where the value stored at each number (index) represents whether that number is a prime. Avoid useless array traversals.
b) For full credit, store only one bit for each number (thus, one byte will store information about being prime or composite for 8 numbers). Write functions that query or set whether a number is compound (implemented by accessing the relevant bits); the function implementing the sieve algorithm itself should contain no bit operations. (Ideally, you should only need to change the check/set prime functions to switch the algorithm from one representation to the other).

2. Implement the standard C function size_t strspn(const char *s, const char *accept) that returns how many characters at the start of s belong to accept, without other characters in between. For instance, strspn("abracadabra", "cba") returns 2: the first two characters belong to "cba", the third one no longer does.

3. Write a function int belongsto(char c, const char *cset) that checks whether c belongs to the set of characters represented by string cset . In latter, a character range c1-c2 represents all characters with values at least c1 and at most c2. Other individual characters represent themselves. Thus, "0-9A-z,a-f" represents digits, upperchase letters, the comma, and lowercase letters up to f. A dash (minus) as first or last character of the string represents itself (since it is not separating the endpoints of a range). If two ranges share an endpoint: c1-c2-c3, they represent the union of the ranges c1-c2 and c2-c3.

Marius Minea

Last modified: Sun Nov 3 19:00:00 EEST 2013