# Generate all prime numbers up to N

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

```