Prime Generator - PRIME1

test1.cpp

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	//For Fast IO
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	//Sieve of Eratosthenes - Start
	long int N = 1000000000;
	//We will generate all primes till sqrt(N)
	int prime_limit = int(sqrt(N));
	bool arr[prime_limit+1];
	vector<int> primes;
	fill_n(arr,prime_limit+1,true);
	
	//Start by crossing out multiples of 2
	int prime = 2;
	int limit = int(sqrt(prime_limit));
	while(prime <= limit){
		for(int prime_multiple=prime*prime; prime_multiple<=prime_limit; prime_multiple=prime_multiple+prime){
			arr[prime_multiple] = false;
		}
		for(int next_prime=prime+1; next_prime<=prime_limit; next_prime++){
			if(arr[next_prime]==true){
				prime = next_prime;
				break;
			}
		}
	}
	for(int index=2; index<=prime_limit; index++){
		if(arr[index] == true){
			primes.push_back(index);
		}
	}
	//Sieve of Eratosthenes - End

	int t,m,n;
	cin>>t;
	for(int testcase=0; testcase<t; testcase++){
		cin>>m>>n;
		//There are no primes less than 2
		if(m < 2){
			m = 2;
		}
		//Case 1: Both m and n within the sqrt(N)
		//No need for segmented sieve
		if(n <= prime_limit){
			//Print all primes that are greater than m and less than n
			for(int i=0; i<primes.size(); i++){
				if(primes[i] >= m && primes[i] <= n){
					cout<<primes[i]<<"\n";				
				}			
			}
		}
		//Segmented Sieve of Eratosthenes
		else if(n > prime_limit){
			bool segmented_arr[n-m+1];
			fill_n(segmented_arr,n-m+1,true);
			int prime_index = 0;
			int prime = primes[prime_index];
			int limit = int(sqrt(n));
			//Incase of 10^9 as n, we check 32607 as last prime, but prime_index+1 goes out of bounds
			//therefore we check if prime_index < primes.size() also
			while(prime <= limit && prime_index < primes.size()){
				int starting_multiple = int(m/prime) * prime;
				if(starting_multiple == 0){
					starting_multiple += prime;
					starting_multiple += prime;
				}
				else if(starting_multiple == prime){
					starting_multiple += prime;
				}
				else if(starting_multiple < m){
					starting_multiple += prime;
				}
				for(int prime_multiple=starting_multiple; prime_multiple<=n; prime_multiple = prime_multiple+prime){
					segmented_arr[prime_multiple-m] = false;
				}
				prime_index += 1;
				prime = primes[prime_index];			
			}
			for(int index=0; index<n-m+1; index++){
				if(segmented_arr[index] == true){
					cout<<index+m<<"\n";
				}	
			}					
		}
	//Empty line at end of each testcase
	cout<<"\n";
	}
	return 0;
}