hi im really frustated about my code since i already optimize my code and still got tle (T^T)
here my code
click here
or
#include<iostream>
#include<stdio.h>
#include<set>
#include<math.h>
using namespace std;
bool isprime(int n)
{
for(int x=3;x<=int(sqrt(n));x+=2)if(n%x==0)return 0;
return 1;
}
int main()
{
set<int> prime;
prime.insert(2);prime.insert(3);prime.insert(5);
prime.insert(7);
for(int x=9;x<=32000;x+=2)
{
if(isprime(x))prime.insert(x);
}
set<int>::iterator it;
int t;
scanf("%d",&t);
while(t--)
{
int a,b;
scanf("%d %d",&a,&b);
if(b>32000){
if(!(a&1))a++;
for(int x=a;x<=b;x+=2)
{
bool cek=1;
for(it=prime.begin();it!=prime.end();it++)
{
if(*it>int(sqrt(x)))break;
if(x%*it==0){cek=0;break;}
}
if(cek)printf("%d\n",x);
}
}
else
{
for(it=prime.begin();*it<=b && it!=prime.end();it++)
{
if(*it>=a && *it<=b ) printf("%d\n",*it);
}
}
}
}
Your algo is O(n sqrt(n)). the intended solution of the qn is in O(n) which is possible by sieves. read Sieve of Eratosthenes. it is easy to implement
1 Like
@aqua_lauga as said by @kcahdog use sieve of era… as the value of a & b can be upto 10^9 so we need
to first calculate prime numbers upto 32000.
we can do this by sieve…
for a better understanding of sieve of erato read this tutorial
btw here is my solution …if u have any doubt feel free to ask.
#include<stdio.h>
#define max 32000
int prime[max];
int p[max];
int main()
{
for(int i=2;i<max;i++)prime[i]=1;
for(int i=2;i<max;i++){
if(prime[i])
for(int j=i;j*i<max;j++)
prime[i*j]=0;
}
int j=0;
for(int i=2;i<max;i++)
{
if(prime[i])
{
p[j++]=i;
}
}
int t,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&b);
for(int i=a;i<=b;i++)
{
for(int k=0;p[k]*p[k]<=i;k++)
{
if(i%p[k]==0)
goto out;
}
if(i!=1)
printf("%d\n",i);
out:;
}
}
return 0;
}
i think i have a better algo for this
can you try this
public boolean isPrime (int n) { if (n<=1) return false; if (n==2) return true; if (n%2==0) return false; int m=Math.sqrt(n); for (int i=3; i<=m; i+=2)if (n%i==0) return false; return true; }
a
If you are working with primes in big limit it’s easy focus on composites first as they can be easily checked…Or first make an boolean array to store the composites position …simply others are primes…Although you may need more than 0,1…You can do int or char array to store if a number has been worked on or not too.
try to use sieve of erothenese ( its fast …) read it from wikipedia
Programming Tip: As far as possible, never use goto statements. Here, you can use some flags (just variables) and set them when the condition is met. Outside the loop, test the value of this flag, and add code accordingly. Thus, you can avoid goto statements.
Of course, you can use goto, but the use is highly discouraged.
1 Like
@tijoforyou tnx 4 ur tip…this would be more helpful if u can list some disadvantages of using “goto” .
Have you heard about structured programming? Quoting Wikipedia:
Structured programming is a
programming paradigm aimed on
improving the clarity, quality, and
development time of a computer program
by making extensive use of
subroutines, block structures and for
and while loops—in contrast to using
simple tests and jumps such as the
goto statement which could lead to
“spaghetti code” which is both
difficult to follow and to maintain.
So, using goto will make it difficult to follow the pgm flow.
In languages like Java, there is no goto, because of these reasons.
It is not the case that goto is bad. But, it is the case that goto can be made to look bad. Precisely to avoid this reason, goto-less programming is encouraged.
why goto should be avoided - C++ Forum is a discussion on goto-less programming