© Parineeth M R

** Question 50. Generate all the prime numbers that are less than or equal to N**

To generate all prime numbers <= N, we make use of the sieve of Eratosthenes where we do the following 1. We generate the numbers from 2 to N and for each number X, we mark all multiples of X up to N to indicate that these multiples can’t be primes 2. If a number is not a multiple of any of the numbers preceding it, then it is a prime

We skip 0 and 1 as they are not considered to be prime. 2 is the first prime number. Then all multiples of 2 up to N are marked to indicate that these multiples can’t be primes. The next number is 3. Since 3 is not a multiple of any number before it (note that we have skipped 1 and so we ignore the fact that 3 is a multiple of 1), 3 is a prime. We then mark all multiples of 3. The next number is 4. Since 4 has been marked to be a multiple, it can’t be prime. We then mark all the multiples of 4 and this process continues till N

## C/C++

/*sets the bit at position pos to 1 in the bitmap*/ void set_bit(unsigned char bitmap[], int pos) { int byte_pos = pos / 8; int bit_pos = pos % 8; bitmap[byte_pos] |= 1u << bit_pos; } /*Returns the bit at position pos in the bitmap*/ int get_bit(unsigned char bitmap[], int pos) { int byte_pos = pos / 8; int bit_pos = pos % 8; if (bitmap[byte_pos] & (1u << bit_pos) ) return 1; else return 0; } /* n: Upto what number the primes should be generated */ void generate_primes(int n) { int i, j; int total_num_bytes = 1 + (n / 8); /*is_multiple_bmp will be initialized with zeroes since we have not yet identified the multiples*/ unsigned char *is_multiple_bmp = (unsigned char*) calloc(1, total_num_bytes); /*We don't consider 0 and 1 as prime. Start from 2*/ for (i = 2; i <= n; ++i) { if (get_bit(is_multiple_bmp, i)) continue; /*i is a multiple, so it can't be prime*/ printf("%d is prime\n", i); /*Mark all multiples of i (2i, 3i, 4i, etc) starting from 2*i */ for (j = 2*i; j <= n; j += i) { set_bit(is_multiple_bmp, j); } } free(is_multiple_bmp); }

## Java

/* n: Upto what number the primes should be generated */ public static void generatePrimes(int n) { /*isMultiple will be initialized with false since we have not yet identified the multiples*/ boolean[] isMultiple = new boolean[n+1]; /*We don't consider 0 and 1 as prime. Start from 2*/ for (int i = 2; i <= n; ++i) { if (isMultiple[i]) continue; /*i is a multiple, so it can't be prime*/ System.out.println(i + " is prime "); /*Mark all multiples of i (2i, 3i, 4i, etc) starting from 2i */ for (int j = 2*i; j <= n; j += i) { isMultiple[j] = true; } } }

## Python

#n: Upto what number the primes should be generated def generate_primes(n) : #is_multiple will be initialized with False since we have not yet #identified the multiples is_multiple = [False] * (n+1) #We don't consider 0 and 1 as prime. Start from 2 for i in range(2, n+1): if (is_multiple[i]) : continue #i is a multiple, so it can't be prime print('{} is prime '.format(i) ) #Mark all multiples of i (2i, 3i, 4i, etc) starting from 2i for j in range(2*i, n+1, i): is_multiple[j] = True