Generate all prime numbers up to N

© 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