I have been trying to solve a problem on segmented sieve i.e prime1(http://www.spoj.com/problems/PRIME1/) in spoj but i am getting wrong answer and unable to find the bug in the code. So please help me..↵
↵
#include <iostream>↵
#include <cstdio>↵
#include <cmath>↵
#include <map>↵
#define lli long long int↵
#define inf 10000000001↵
using namespace std;↵
int count[1000001];↵
int store[88888];↵
int main() {↵
int p = 2,d = 0;↵
lli n = sqrt(inf);↵
while (p <= n) {↵
store[d++] = p;↵
for (lli j = 2; j <= n/p; j++) {↵
count[p*j] = 1;↵
}↵
int l;↵
for (l = p + 1; l <= n; l++) {↵
if (count[l] == 0) {↵
p = l;↵
break;↵
}↵
}↵
if (l == n + 1) {↵
break;↵
}↵
}↵
int t;↵
scanf("%d",&t);↵
while (t--) {↵
int l,r,x = 0,ct = 0;↵
scanf("%d %d",&l,&r);↵
map <int,int> m1;↵
p = store[x];↵
while (x < d && p <= sqrt(r)) {↵
int z = l/p;↵
if (l % p == 0) {↵
m1[l] = 1;↵
}↵
if (l <= p) {↵
z = 1;↵
}↵
for (int i = z+1; i <= r/p; i++) {↵
m1[p*i] = 1;↵
}↵
p = store[++x];↵
}↵
for (int i = l; i <= r; i++) {↵
if (i == 1) {↵
continue;↵
}↵
if (m1[i] == 0) {↵
printf("%d\n",i);↵
}↵
}↵
printf("\n");↵
}↵
return 0;↵
}http://ideone.com/JiSxel
↵
#include <cstdio>↵
#include <cmath>↵
#include <map>↵
#define lli long long int↵
#define inf 10000000001↵
using namespace std;↵
int count[1000001];↵
int store[88888];↵
int main() {↵
int p = 2,d = 0;↵
lli n = sqrt(inf);↵
while (p <= n) {↵
store[d++] = p;↵
for (lli j = 2; j <= n/p; j++) {↵
count[p*j] = 1;↵
}↵
int l;↵
for (l = p + 1; l <= n; l++) {↵
if (count[l] == 0) {↵
p = l;↵
break;↵
}↵
}↵
if (l == n + 1) {↵
break;↵
}↵
}↵
int t;↵
scanf("%d",&t);↵
while (t--) {↵
int l,r,x = 0,ct = 0;↵
scanf("%d %d",&l,&r);↵
map <int,int> m1;↵
p = store[x];↵
while (x < d && p <= sqrt(r)) {↵
int z = l/p;↵
if (l % p == 0) {↵
m1[l] = 1;↵
}↵
if (l <= p) {↵
z = 1;↵
}↵
for (int i = z+1; i <= r/p; i++) {↵
m1[p*i] = 1;↵
}↵
p = store[++x];↵
}↵
for (int i = l; i <= r; i++) {↵
if (i == 1) {↵
continue;↵
}↵
if (m1[i] == 0) {↵
printf("%d\n",i);↵
}↵
}↵
printf("\n");↵
}↵
return 0;↵
}
