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[2]=1;
p[1]=p[0]=0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin>>n;
int p[100000]={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 format your code using ``` before and after code.
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[0]=prime[1]=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[2]=1;
p[1]=p[0]=0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin>>n;
int p[100000]={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[2]=1;
p[1]=p[0]=0;
}
int main()
{
int n;
cin>>n;
int p[100001]={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[2]=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 :
- Iterators are long long, it is not recommended since int can be used for iterating over array.
- You are using i<=100000, which will cause segmentation fault. You are accessing an index out of range.
- 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[100001];
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[0]=isprime[1]=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.
Link1
Link2
Link3
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[2]=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[2]=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 ?