0
Your rating: None

CodeChef submission 271732 (C++ 4.3.2)

CodeChef submission 271732 (C++ 4.3.2) plaintext list. Status: TLE, problem PRIME1, contest . By opeth (opeth), 2010-06-22 21:53:05.
  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<vector>
  6. #include<stdio.h>
  7. #include<time.h>
  8. #define prime 0
  9. #define notprime 1
  10. #define FOR(i,a) for(i=0; i<a; i++)
  11. using namespace std;
  12.  
  13. bool isPrime[32000] = {0};
  14. vector<int> primes;
  15. //prime = new int[3500];
  16. void primesMN(int m, int n, bool primeMN[]);
  17. void sieve()
  18. {//Eratosthenes Sieve	
  19. 	/*int i=0, cur, end=0, count;
  20. 	isPrime[0] = isPrime[1] = notprime;
  21. 	cur = 2;
  22. 	while(!end)
  23. 	{
  24. 	for(i=2*cur; i<32000; i=i+cur)
  25. 		isPrime[i] = notprime;
  26. 	while(1)
  27. 	{
  28. 	if((cur+1)==32000) {end=1; break;}
  29. 	if(isPrime[cur+1]==prime) {cur++; break;}
  30. 	else cur++;
  31. 	}
  32. 	}
  33. 	count = 0;
  34. 	for(i=0; i<32000; i++)
  35. 	{
  36. 	if(isPrime[i]==0)
  37. 		{
  38. 		prime[count] = i;
  39. 		count++;
  40. 		}
  41. 	}*/
  42.      int i, j, flag=1;
  43.      primes.push_back(2);
  44. 	for(i=3; i<32000; i++)
  45. 	{
  46. 	flag = 1;
  47. 	for(j=0; j<primes.size(); j++)
  48. 		{
  49. 		if(i%primes[j]==0) {flag=0; break;}
  50. 		}
  51. 	if(flag)
  52. 	primes.push_back(i);
  53. 	else continue;
  54. 	}
  55. }
  56.  
  57. int main()
  58. {
  59. int m, n, t;
  60. sieve();
  61. scanf("%d", &t);
  62. while(t--)
  63. {
  64. bool primeMN[100002] = {0};
  65. scanf("%d %d", &m, &n);
  66. primesMN(m, n, primeMN);
  67. }
  68. return 0;
  69. }
  70. void primesMN(int m, int n, bool primeMN[])
  71. {
  72. int index = 0, i, mul, nonPrime;
  73. while(1)
  74. {
  75. for(i=0; i<=n-m; i++)
  76. 	{
  77. 	if((i+m)%primes[index]==0)
  78. 		{
  79. 		mul = i;
  80. 		break;
  81. 		}
  82. 	}
  83. if(primes[index]==(mul+m))
  84. 	nonPrime = primes[index] + mul;
  85. else nonPrime = mul;
  86. for(i=nonPrime; i<=n-m; i+=primes[index])
  87. 	{
  88. 	primeMN[i] = notprime;
  89. 	}
  90. index++;
  91. if(primes[index]==31991||primes[index]>=n) break;
  92. }
  93. i=0;
  94. if(m==1) i=1;
  95. for(;i<=n-m;i++)
  96. 	{
  97. 	if(primeMN[i]==prime)
  98. 	printf("%d\n", i+m);
  99. 	}
  100. }

Comments