Skip to main content

Find the prime numbers between a range of numbers

Often this question is asked in interviews by companies and most of them apply the same old traditional method of finding prime numbers resulting in large complexity of the program. The proper solution for finding the prime numbers is the Sieve of Eratosthenes. Well, the algorithm is not so difficult, unlike its name. The basic principle here is to iteratively mark the multiples of unmarked numbers starting from 2 till the limit and then the numbers left out unmarked are primes numbers.

Let's take a series of numbers starting from 2.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............

Now lets mark multiples of 2

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............

Now mark multiples of 3 (Next unmarked)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............

Now mark the multiples of next unmarked that is 5

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..............

Now mark the multiples of next unmarked and so on upto the limit.The numbers which are left unmarked till the end of iteration are Prime numbers.

Algorithm :

 Input the integer numbers between 2 to n.

Let arr be array of values from 2 to n.All initialised to Zero.

Let the first number p=2.Mark all the multiples of 2 that is 2p,3p,4p...and so on and change its value in array to 1

Repeat the iteration till the end of array.

The number left with 0 value in array are prime numbers.Print them.

Pseudo Code :

 arr[i]={0,0,0,......};
for i=2,3,4......
if arr[i]==0
for j=i^2, i^2+i, i^2+2i, i^2+3i.... // i^2 is used instead of 2i,3i considering the fact that the previous numbers           ...                                                                                            are already marked
arr[j]==1;
All arr[i] which is 0 are prime numbers.

The complexity of algorithm is O(n(logn)(loglogn)) bit operations and for memory requirement O(n).You can use this algorithm to find a prime number between the range of numbers in an interview as the program has moderate complexity.There are other algorithms also but Sieve of Eratosthenes is the simplest one.
Have a look at it

Sieve of Atkin
Sieve of Sundaram



Labels:

Comments

Post a Comment

Popular posts from this blog

Tricky Questions or Puzzles in C ( Updated for 2026)

Updated for 2026 This article was originally written when C/C++ puzzles were commonly asked in interviews. While such language-specific puzzles are less frequent today, the problem-solving and logical reasoning skills tested here remain highly relevant for modern Software Engineering, Data Engineering, SQL, and system design interviews . Why These Puzzles Still Matter in 2026 Although most Software &   Data Engineering interviews today focus on Programming, SQL, data pipelines, cloud platforms, and system design , interviewers still care deeply about how you think . These puzzles test: Logical reasoning Edge-case handling Understanding of execution flow Ability to reason under pressure The language may change , but the thinking patterns do not . How These Skills Apply to Data Engineering Interviews The same skills tested by C/C++ puzzles appear in modern interviews as: SQL edge cases and NULL handling Data pipeline failure scenarios Incremental vs ...
23 comments
Read more

Decorators in Python

Decorators provide additional functionality to the functions without directly changing their definition of them. Basically, it takes the functions as an argument, adds functionality to them, and returns it.  Before diving deep into the concept of Decorators, let's first try to understand  What are functions in Python and what is an inner function? In Python everything is Objects, be it Class, Variables, and Functions . So functions are python first-class objects that can be used or passed as an argument. You can store the functions in variables, you can pass a function to another function as parameters, and you can also return the function from the function. Below is one simple example where we are treating functions as objects . def make_me_lowercase ( str ): return str .lower() print (make_me_lowercase( "HELLO World" )) copy_of_you = make_me_lowercase print (copy_of_you( "HELLO World" )) The output of the above calls for both the functio...
2 comments
Read more

Program to uncompress a string ie a2b3c4 to aabbbcccc

Below is the program to uncompress a string #include<stdio.h> #include<conio.h> #include<stdlib.h> int main() { char str[100]="a2b3c4d8u7"; for(int i=0;str[i]!='\0';i++) { if(i%2!=0) { for(int j=0;j<atoi(&str[i]);j++) { printf("%c",str[i-1]); } } } getch(); } Want to become a Data Engineer? Check out below blog posts  1.  5 Key Skills Every Data Engineer needs in 2023 2.  How to prepare for Data Engineering Interviews 3.  Top 25 Data Engineer Questions
2 comments
Read more