 # Prime_sieve

I have tried for 2 days to understand the concept of the sieve algorithm and I have clear all the concepts of this algorithm and I wanted to write the code of this problem I have no idea where I am doing a mistake. can anyone help me in this Algorithm my code is here

Share your code , i will clear your all doubt regarding prime and sieve.

``````#include<bits/stdc++.h>
using namespace std;

void prime_sieve(int *p)
{
//mark all odd number is prime number
for(int i=3;i<=100000;i=i+2)
{
p[i]=1;
}
//mark all the multiple odd number is not prime number
for(long long i=3;i<=100000;i=i+2)
{
if(p[i]==1)
{
for(long long  j=i*i;j<=100000;j=j+i)
{
p[j]=0;
}
}
}
p=1;
p=p=0;

}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin>>n;
int p={0};
prime_sieve(p);
for(int i=0;i<=n;i++)
{
if(p[i]==1)
{
cout<<i<<" ";
}
}
return 0;
}
``````

hii bro this my code pls help me

Please share the problem statement and your solution here. We will check and clear your doubts. ok

Wait what u wanna do , this is completely wrong code .

``````#define MAX 100000000
bool prime[MAX+1];

void Prime_sieve(){ //prime or not
for(int i=0;i<=MAX;i++) prime[i]=1;
prime=prime=0;

for(lli i=4;i<=MAX;i+=2) prime[i]=0;

for (int p=3; p*p<=MAX; p+=2){
if (prime[p] == 1){
for (int i=p*2; i<=MAX; i += p){
prime[i] = 0;
}
}
}
}

int main()
{
for(lli i=1;i<MAX;i++)
if(prime[i])
cout<<i<<" ";
}
``````
``````
#include<bits/stdc++.h>
using namespace std;

void prime_sieve(int *p)
{
//mark all odd number is prime number
for(int i=3;i<=100000;i=i+2)
{
p[i]=1;
}
//mark all the multiple odd number is not prime number
for(long long i=3;i<=100000;i=i+2)
{
if(p[i]==1)
{
for(long long  j=i*i;j<=100000;j=j+i)
{
p[j]=0;
}
}
}
p=1;
p=p=0;

}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin>>n;
int p={0};
prime_sieve(p);
for(int i=0;i<=n;i++)
{
if(p[i]==1)
{
cout<<i<<" ";
}
}
return 0;
}

``````

Here u go -

``````#include<bits/stdc++.h>
using namespace std;

void prime_sieve(int *p)
{
//mark all odd number is prime number
for(int i=3;i<=100000;i=i+2)
{
p[i]=1;
}
//mark all the multiple odd number is not prime number
for(long long i=3;i<=100000;i=i+2)
{
if(p[i]==1)
{
for(long long  j=i*i;j<=100000;j=j+i)
{
p[j]=0;
}
}
}
p=1;
p=p=0;

}
int main()
{

int n;
cin>>n;
int p={0};
prime_sieve(p);
for(int i=0;i<=n;i++)
{
if(p[i]==1)
{
cout<<i<<" ";
}
}
return 0;
}
``````

bro my concept was i was mark all the odd number as prime in first loop then mark all the multiple of odd number is not prime number that’s it

actually u use freeopen and all , they are only for online judge , so your code didn’t print anything , one more thing u have to initalize P array with 100001 not 100000 as last index is 99999

``````bool prime[size]={false};
void sieve()
{
prime=true;
for(int i=3;i<size;i+=2)
prime[i]=true;
for(int i=3;i*i<size;i+=2)
if(prime[i])
for(int j=i*i;j<size;j+=i)
prime[j]=false;
}
``````

This is bit clear approach.
Mistakes I found in your code :

1. Iterators are long long, it is not recommended since int can be used for iterating over array.
2. You are using i<=100000, which will cause segmentation fault. You are accessing an index out of range.
3. Time complexity of your program is not O(n(log(log(n)))), it’s slightly more.

Once recheck with the Actual Algorithm here. 2 Likes

basically the above code runs in nloglog(sqrt(n))

// c++ full code for printing prime till nmax ,basically we mark the multiples as false in the array and print the true ones that is isprime==true.

``````
#include <iostream>
using namespace std;
#include<bits/stdc++.h>
typedef long long ll;

bool isprime;
ll nmax=100001;

int main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);

memset(isprime,true,sizeof(isprime));  // set all the numbers as prime==true in the isprime array
isprime=isprime=false;

for(int i=2;i<nmax;i++)  // put them to filter
{
if(isprime[i])       // for i=2 starting from 2 mark all multiples of 2 as false ie>2))>> 4,6,8,10
//for i= 3 is true so it will  be a prime number  mark its multiple as false
//3))>>6,9,12
//do this for every isprime==true  number
//finally u will get isprime array filled with true and false .

{

for(int j=2*i;j<nmax;j+=i)
{
isprime[j]=false;
}

}
}

for(int i=0;i<nmax;i++)
{
if(isprime[i])
{
cout<<i<<" ";  // print the prime number which has isprime==true.
}
}
}``````

No, I guess you have mistaken. Time complexity of my code is not sqrt(n)*log(log(n)), it is nlog(logn)), according to my knowledge.
The below links state the time complexity of sieve is O(nlog(logN))). Correct me if I am wrong.

1 Like

thankyou so much bro finally i understand this algorithm

thanks for these links 1 Like

Happy Coding. 1 Like

outer loop is rootN

``````bool prime[size]={false};
void sieve()
{
prime=true;
for(int i=3;i<size;i+=2)
prime[i]=true;
for(int i=3;i<size;i+=2)
if(prime[i])
for(int j=i*i;j<size;j+=i)
prime[j]=false;
}

``````
``````bool prime[size]={false};
void sieve()
{
prime=true;
for(int i=3;i<size;i+=2)
prime[i]=true;
for(int i=3;i*i<size;i+=2)
if(prime[i])
for(int j=i*i;j<size;j+=i)
prime[j]=false;
}
``````

what is complexities of both code ?