Hey i was trying SPOJ prime-generator problem and i have written my code for it and it gives correct output but SPOJ still showing that answer is wrong.
My code is below please tell why my code is wrong
#include
using namespace std;
int t,i,j;
long long m,n;
int primegenerator(long long x);
int main()
{
cin >> t;
for(i=0;i> m >> n;
for(j=m;j<=n;j++)
{
primegenerator(j);
}
}
return 0;
}
int primegenerator(long long x)
{
int k;
for(k=2;k<=sqrt(x);k++)
{
if(x%k==0)
return 0;
}
cout << x << endl;
}
optimize the code in primegenerator() function, by using this:
if(x%2==0)
return 0;
else{
for(int i=3;i*i<=x;i=i+2){
if(x%i==0)
return 0;
}
}
you can also use sieve of eratosthenes for finding primes, fast and efficient:
my code link: BDUVbj - Online C++0x Compiler & Debugging Tool - Ideone.com
link for sieve of eratosthenes: Sieve of Eratosthenes - GeeksforGeeks
1 Like
@neilit1992
Your code link is not visible.
Please give a link which i can see don’t make it private.
1 Like
Code link was private, made it public, check it now.
1 Like
/*
* spoj3.c
*
* Created on: 19-Feb-2016
* Author: Neil
/
#include<stdio.h>
#include<string.h>
int prime[32001];
int p[100001];
void sieve()
{
prime[1]=1;
int i,j;
for(i=2;ii<=32000;i++)
if(!prime[i])
for(j=2*i;j<=32000;j+=i)
prime[j]=1;
}
int main()
{
int i,j,t,m,n,v;
sieve();
scanf("%d",&t);
while(t--){
scanf("%d%d",&m,&n);
if(m<2)
m=2;
memset(p,0,sizeof(p));
for(i=2; i*i<=n; i++)
if(!prime[i])
{
v=((m-1)/i+1)*i;
for(j=v==i?i<<1:v; j<=n; j+=i)
p[j-m]=1;
}
for(i=0; i<=n-m; i++)
if(!p[i])
printf("%d\n",i+m);
printf("\n");
}
return 0;
}
Dude do not post solution,Instead of that give some hints only.
1 Like