fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<vector>
  3. #include<algorithm>
  4. #define MAX 100000
  5. using namespace std;
  6. vector<long long> pri;
  7. void preprocess()
  8. {
  9. 	long long arr[MAX];
  10. 	for(long long i=0; i<MAX; i++)
  11. 		arr[i]=1;
  12. 	arr[0]=arr[1]=0;
  13.  
  14. 	for(long long i=2;i<MAX;i++)
  15. 	{
  16.  
  17. 		if(arr[i]==1)
  18. 		{
  19.  
  20. 			pri.push_back(i);
  21. 			for(long long j=i*i;j<MAX;j=j+i)
  22. 				arr[j]=0;
  23. 		}
  24. 	}
  25. }
  26. void result(int low, int high)
  27. {
  28. 	int len=high-low+1;
  29. 	int arr[len];
  30. 	for(int i=0;i<len;i++)
  31. 		arr[i]=1;
  32. 	if(low==1)
  33. 		arr[0]=0;
  34. 	for(int i=0;pri[i]*pri[i]<=high;i++)
  35. 	{
  36. 		int temp=(low/pri[i])*pri[i];
  37. 		if(temp<low)
  38. 			temp+=pri[i];
  39. 		for(int j=temp-low;j<len;j+=pri[i])
  40. 				if(j!=pri[i])
  41. 					arr[j]=0;
  42. 	}
  43.  
  44. 	for(int i=0;i<len;i++)
  45. 		if(arr[i])
  46. 			printf("%d\n",i+low);
  47. }
  48. int main()
  49. {
  50. 	int test, a ,b;
  51. 	preprocess();
  52. 	scanf("%d",&test);
  53. 	while(test--)
  54. 	{
  55. 		scanf("%d%d",&a,&b);
  56. 		result(a,b);
  57. 		printf("\n");
  58. 	}
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 4136KB
comments (?)
stdin
copy 
2
1 100
1 10
stdout
copy 
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

5
7
https://ideone.com/KdltlA
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!