include cmath include cstdio include cstdlib long long pow long long l

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cmath>
#include <cstdio>
#include <cstdlib>
long long pow(long long a, long long b, long long c)
{
while (b--)
{
a=(a%c*a%c)%c;
}
return a;
}
void gen_primes(long long start, long long end)
{
int trials=5;
if (start<2) printf("2\n");
if (end==2) { printf("2\n"); return;}
long long n = start;
long long m = end-(end+1)%2;
if (m<2) return;
long long v = (long long)(ceil(log( m ) / log( 2 )))+2;
long long d = m;
long long e = 1;
long long cent_primes[24]={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
if ( (n <= 100) || (m <= 100) )
{
for(int i =0; i<24; i++)
{
if (cent_primes[i] < n) continue;
if (cent_primes[i] > m) break;
printf("%lld\n",cent_primes[i]);
}
}
if (n <= 1) n = 2;
n -= 1;
if (n%2 == 0) n -= 1;
for (int s=2; s<v; s++)
{
d >>= 1;
e <<= 1;
long long f= e<<1;
long long p=-e;
long long h = int(ceil((n-e)/f)) + 1;
p += h*f + 1;
for (long long r=h*2+1; r<d+1; r+=2)
{
p += f;
int z = p%6;
if ( (z != 1) && (z != 5) ) continue;
int end1=1;
for (int i=0; i<24; i++)
{
if (p%cent_primes[i]==0) { end1=0; break; }
}
if (end1)
{
long long o = p - 1;
int end3=1;
for (int i=0; i<5; i++)
{
long long y = pow((rand()+1)%o,r,p);
if (y == 1) continue;
int end2=0;
for (long long j=1; j<s; j++)
{
if (y==o) { end2=1; break; }
y = ((long long)pow(y,2))%p;
}
if (end2) { end3=0; break; }
}
if (end3) printf("%lld\n",p);
}
}
}
}
int main()
{
int cases;
scanf("%d\n",&cases);
while (cases--)
{
long long m,n;
scanf("%lld %lld\n",&n,&m);
gen_primes(n,m);
printf("\n");
}
}