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



Comments

Post a Comment

Popular posts from this blog

Tricky Questions or Puzzles in C

-
This post is about the Tricky Questions   or code snippet in C or C++ asked in most of the Interviews   (See Interview Experience ) by some of the good companies. You may know probably the right concept but it will not strike you at the interview and to crack all those Interview Questions  you should know some of them beforehand. If you are applying for Job related to JAVA then checkout the blog post  Tricky Questions in JAVA . 1) what will be the output of the following Printf function.   printf("%d",printf("%d",printf("%d",printf("%s","ILOVECPROGRAM")))); Ans-ILOVECPROGRAM1321 The above printf line gives output like this because printf returns the number of character successfully written in the output. So the inner printf("%s","ILOVECPROGRAM") writes 13 characters to the output so the outer printf function will print 13 and as 13 is of 2 characters so the next outer printf function will print 2 and then
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
Read more

Programs and Puzzles in technical interviews i faced

-
Image
I have attended interview of nearly 10 companies in my campus placements and sharing their experiences with you,though i did not got selected in any of the companies but i had great experience facing their interviews and it might help you as well in preparation of interviews.Here are some of the puzzles and programs asked to me in interview in some of the good companies. CHECK-OUT the VIDEO of  Technical Interview for SAP Labs, CA Tech & HP R&D 1) SAP Labs I attended sap lab online test in my college through campus placements.It had 3 sections,the first one is usual aptitude questions which i would say were little tricky to solve.The second section was Programming test in which you were provided snippet of code and you have to complete the code (See Tricky Code Snippets  ).The code are from different data structures like Binary Tree, AVL Tree etc.Then the third section had questions from Database,OS and Networks.After 2-3 hours we got the result and i was shortlisted
Read more