Segmented Sieve-All Primes in Range

/* Bismillahir Rahmanir Rahim Segmented Sieve-Prime number in big range (10^14). Given two number (10^14) and given all primes in range. First execute all the primes bellow sqrt(b). */ #include<bits/stdc++.h> #define ll long long using namespace std; ll t, a, b, p, st, i, j, k; bool prime[10000007], ar[1000006]; void primes(ll x){ // mind, 2 is prime for(ll i=3; i*i<=x; i+=2){ if(prime[i]){ for(ll j=i*3; j<=x; j+=i*2) prime[j]=false; } } } int main(){ while(cin>>a>>b){ p=sqrt(b+1); for(i=0; i<=p; i++) prime[i]=true; for(i=0; i<=(b-a); i++) ar[i]=true; primes(p); for(i=3; i<=p; i+=2){// we don't execute the even number if(prime[i]){ st=a; if(st%i) st=a+(i-(st%i)); // use i not ar[i] if(st==i) st=st*2; //if the first number is prime for(k=st; k<=b; k+=i) ar[k-a]=false; } } if(a==2) cout<<2<<" "; // special case st=0; if(a%2==0) st=1; // its for skipping even number for(i=st; i<=(b-a); i+=2){ //we don't touch even number if(ar[i]) cout<<i+a<<" "; } cout<<endl; } return 0; } /* Input: 100000000000000 100000000100000 Output: (big output, to see run the code) */

Sieve-All Primes from 2 to n

/* Bismillahir Rahmanir Rahim Sieve-all primes from 1 to n */ #include<bits/stdc++.h> #define ll long long using namespace std; bool ar[10000009]; void sieve(ll x){ for(int i=3; i*i<=x; i+=2){ if(ar[i]){ for(int j=i*3; j<=x; j+=i*2) ar[j]=false; } } } int main(){ ll n, k; while(cin>>n){ memset(ar, true, sizeof(ar)); sieve(n); cout<<2<<" "; for(k=3; k<=n; k+=2){ if(ar[k])cout<<k<<" "; } cout<<endl; } return 0; }

Primality Checking

/* Bismillahir Rahmanir Rahim Time Complexity: O(sqrt(n)/2) */ #include<bits/stdc++.h> #define ll long long using namespace std; ll n, i; bool isPrime(int n){ if(n<2 || (n!=2 && n%2==0)) return false; else{ for(i=3; i*i<=n; i+=2){ if(n%i==0) return false; } } return true; } int main(){ while(cin>>n){ if(isPrime(n)) cout<<"Prime"<<endl; else cout<<"Not Prime"<<endl; } return 0; }