0
Your rating: None

CodeChef submission 272144 (C++ 4.3.2)

CodeChef submission 272144 (C++ 4.3.2) plaintext list. Status: TLE, problem PRIME1, contest . By opeth (opeth), 2010-06-23 20:22:01.
  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. int primes[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.  
  43. }*/
  44. int MakePrimes3(int limit)
  45. {
  46. primes[0]=2, primes[1]=3, primes[2]=5;
  47.  
  48. int maybeprime = primes[2] + 2;
  49. int *primePtr = primes;
  50. for(int j=3; j<limit; j++)
  51. {
  52. 	for(;;)
  53. 	{
  54. 	int currentprime = *(primePtr++);
  55. 	long int currentprime2 = currentprime * currentprime;
  56.  
  57. 	if(currentprime2 > maybeprime)
  58. 		{
  59. 		primes[j] = maybeprime;
  60. 		primePtr = primes + 1;
  61. 		maybeprime += 2;
  62. 		break;
  63. 		}
  64.  
  65. 	if(maybeprime % currentprime == 0)
  66. 		{
  67. 		maybeprime += 2;
  68. 		primePtr = primes + 1;
  69. 		}
  70. 	}
  71. }
  72. }
  73.  
  74. int main()
  75. {
  76. int m, n, t;
  77. MakePrimes3(3432);
  78. scanf("%d", &t);
  79. while(t--)
  80. 	{
  81. 	bool primeMN[100002] = {0};
  82. 	scanf("%d %d", &m, &n);
  83. 	primesMN(m, n, primeMN);
  84. 	}
  85. return 0;
  86. }
  87. void primesMN(int m, int n, bool primeMN[])
  88. {
  89. int index = 0, i, mul, nonPrime;
  90. while(1)
  91. {
  92. for(i=0; i<=n-m; i++)
  93. 	{
  94. 	if((i+m)%primes[index]==0)
  95. 		{
  96. 		mul = i;
  97. 		break;
  98. 		}
  99. 	}
  100. if(primes[index]==(mul+m))
  101. 	nonPrime = primes[index] + mul;
  102. else nonPrime = mul;
  103. for(i=nonPrime; i<=n-m; i+=primes[index])
  104. 	{
  105. 	primeMN[i] = notprime;
  106. 	}
  107. index++;
  108. if(primes[index]==31991||primes[index]>=n) break;
  109. }
  110. i=0;
  111. if(m==1) i=1;
  112. for(;i<=n-m;i++)
  113. 	{
  114. 	if(primeMN[i]==prime)
  115. 	printf("%d\n", i+m);
  116. 	}
  117. }

Comments