Prime visits using sieve

#1

what is wrong in my code?
#include<bits/stdc++.h>
using namespace std;
bool prime_check(int a)
{
int prime[1000000];
for(int i=2;i<1000000;i++)
prime[i]=1;
prime[1]=0;
for(int i=2;i<1000000;i++)
{
if(prime[i]==1)
{
for(int j=i*2;j<pow(10,6);j+=i)
{
prime[j]=0;
}
}
}
if(prime[a]==1)
return true;
else
return false;
}
int main()
{
int test;
cin>>test;
while(test–)
{
int a,b;
cin>>a>>b;
int count=0;
for(int i=a;i<=b;i++)
{
if(prime_check(i)==true)
count++;
}
cout<<count<<" "<<endl;

}
return 0;

}

#2

in first for loop condition should be ii<1000000 and in the second loop j should be (j=ii).
Also add the problem link.

#3

still not working
#include<bits/stdc++.h>
using namespace std;
bool prime_check(int a)
{
int prime[1000000];
for(int i=2;i<1000000;i++)
prime[i]=1;
prime[1]=0;
for(int i=2;ii<=1000000;i++)
{
if(prime[i]==1)
{
for(int j=ii;j<1000000;j+=i)
{
prime[j]=0;
}
}
}
if(prime[a]==1)
return true;
else
return false;
}
int main()
{
int a,b;
cin>>a>>b;
int count=0;
for(int i=a;i<=b;i++)
{
if(prime_check(i)==true)
count++;
}
cout<<count<<" "<<endl;

return 0;
}

#4

Add the question link and copy your code on ide and share the link.

#5

https://ide.geeksforgeeks.org/I087nnZFWe

#6

Add the question link also.

#7 
  int prime[1000000];
    for(int i=2;i<1000000;i++)
        prime[i]=1;
    prime[1]=0;
    prime[0]=0;
    for(int i=2;i * i<1000000;i++)
    {
        if(prime[i]==1)
        {
            for(int j=i * i;j<1000000;j+=i)
            {
                prime[j]=0;
            }
        }
    }

this code is for seive.

#8

I am assuming you have to find the total number of primes between the interval in the best possible way.
for that you can also maintain a prefix array which stores the prime number between 1 to that number and finally you can print the answer as prefix[b]-prefix[a-1] //this tells you the prime number bewteen the interval a and b.
you can refer this code also :https://ide.geeksforgeeks.org/iqOU1A12aK

#9

isnt this dynamic programming approach?
we are storing the number of primes till that point in an array?

#10

Hi Shubham, this method is called Sieve of Eratosthenes. The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so. You can study more about it.

#11

okay mam thanks:smiley: