When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

GreedyXploit's blog

By GreedyXploit, history, 3 years ago, In English

QUESTION LINK

MY CODE _

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

using namespace std;

vector<long long> SimpleSieve( vector<long long>& primes)
{
	//vector<long long> primes;
	bool isprime[10001]; // 10^5
	for(long long  i = 0 ; i<=10000 ; i++)
		isprime[i] = true;

	for(long long i = 2 ; i*i<=10000 ; i++)
	{
		if(isprime[i])
		{
			
			for(long long j = i*i ; j<=10000 ; j+=i)
				isprime[j] = false;
		}
	}
	for(int i = 0 ; i<=10000 ; i++){
		if(i == 1 || i == 0) continue;
		if(isprime[i] )
			primes.push_back(i);
	}
	return primes;
	
}

int main()
{
	int t;
	cin>>t;
	vector<long long> primes;
	SimpleSieve(primes);
	//for(auto i : primes)
	//	cout<<i<<"\n";

	while(t--){
		long long l , r;
		cin>>l>>r;
		///long long rsqrt = sqrt(r);
	
	bool is_prime[r-l+1];
	for(long long  i =0 ; i<=r-l ; i++)
	{
		is_prime[i] = true;
	}	
		//cout<<i;
	for(long long  i = 0 ;primes[i]*(long long)primes[i]<=r ; i++)
	{
		long long currprime = primes[i];
		//cout<<currprime<<"C"<<"\n";
		long long base = (l/currprime)*(currprime);
		if(base<l)
			base = base + currprime;
		for(long long j = base ; j<=r ; j+=currprime)
		{
			is_prime[j-l] = false;
	
		}	
		if(base == currprime)
			is_prime[base - l] = true;
	}
	
	
	for(long long i = 0 ; i<=r-l; i++)
	{
		if(is_prime[i] == true)
			cout<<i+l<<"\n";
	}
	}
}
  • Vote: I like it
  • -35
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

You put up the same question yesterday, and I replied to it. There's no need to spam.