i want a code to find prime numbers in a given range using while loop.

general
1

#include<stdio.h>
#include<conio.h>
void main()
{ int x,z,y=2;
//x is lower limit and z is upper limit of range
printf(“enter the no.”);
scanf("%d%d",&x&z);
while(x<=z)
{
while(y<=x)
{
if(x%y==0)
{
break;
}
y++;
if(x==y)
printf(“prime no.=%d \n”,x);

    }
    x++;
}
getch();
}

what would be the output??

2

Que: What would be the output??

Ans: compilation error.

Change your scanf statement to

scanf("%d %d",&x,&z);
                ^

Also for finding a prime number, your implementation is wrong.

try this way

if(x<=2 && z>=2)
printf("prime no.=2 \n");
while(x<=z)
{
    y=2;
    while(y<=x)
    {
        if(x%y==0)
       {
         break;
       }
       y++;
       if(x==y)
       printf("prime no.=%d \n",x);

   }
    x++;
}
3

Read more about sieves, @vinayawsm’s algorithm is probably ok (didn’t test it), but with that slow implementation complexity is O(N2), what is something you cannot use for z=100.000, with sieves you can get the results for z=10.000.000

For example I wrote something about sieves here.

As a related problems you can try KPRIME.

1 Like
4

The idea used for generating prime numbers in a range is known as a segmented sieve. I would suggest you first look at the normal sieve of Eratosthenes . In normal sieve you eliminate all factors of the number starting from 1. .For this problem ,we need to cancel out the factors of numbers starting from the closest possible number to the starting of the segment interval to make it run in time.

Please look at the submissions for this problem for code.

5

@betlista yup true. I have given a slow propagation code. It was just the edited version of his actual code so that he could understand better.

6

:slight_smile: segmented sieve is the best option for prime number generation in a given range but when range is very large space complexity also becomes very high . We can use a bit of different version of segmented sieve i.e bit segmented sieve … then only in one integer value we can store 64 flags :slight_smile: 64 because we don’t need to store flags for even numbers Thus reducing the space complexity 64 times :slight_smile:

7

just so you know, “using while loop” means nothing at all, since a for loop can be rewritten as a while loop