fork download
copy 
  1. #include<stdio.h>
  2. #include<list>
  3. #include<algorithm>
  4. #define MAX 10000000
  5. using namespace std;
  6. long long primes[MAX],cost[MAX];
  7. long long arr[355][355],row;
  8. list <long long> rr,cc;		//Row and column list to be used bfs
  9. void sieve()
  10. {
  11. 	long long count=1;
  12. 	for(long long i=0;i<MAX;i++)
  13. 		primes[i]=1;
  14. 	primes[0]=primes[1]=0;
  15. 	for(long long i=2;i<MAX;i++)
  16. 	{
  17. 		if(primes[i])
  18. 		{
  19. 			primes[i]=count;
  20. 			count++;
  21. 			for(long long j=i*i;j<MAX;j+=i)
  22. 				primes[j]=0;
  23. 		}
  24. 	}
  25. }
  26. void find_cost()
  27. {
  28. 	for(long long i=0;i<MAX;i++)
  29. 	{
  30. 		if(primes[i])
  31. 			cost[i]=primes[i]-1;
  32. 		else
  33. 		{
  34. 			if(i%2==0)
  35. 				cost[i]=i/2;
  36. 			else
  37. 				cost[i]=(i+3)/2;
  38. 		}
  39. 	}
  40. }
  41. long long type_of_num(long long num)	//checks number is even, odd or prime
  42. {
  43. 	long long type=0;		//1 for prime, 2 for even and 3 for odd
  44. 	if(primes[num])
  45. 		type=1;
  46. 	else
  47. 	{
  48. 		if(num%2==0)
  49. 			type=2;
  50. 		else
  51. 			type=3;
  52. 	}
  53. 	return type;
  54. }
  55. void bfs(long long r,long long c)		//start row and start column
  56. {
  57. 	rr.push_back(r);
  58. 	cc.push_back(c);
  59.  
  60. 	while(!rr.empty())
  61. 	{
  62.  
  63. 		r=rr.front();
  64. 		c=cc.front();
  65.  
  66. 		long long type=type_of_num(arr[r][c]);
  67.  
  68. 		arr[r][c]=-1;		//Present grid visited
  69. 		rr.pop_front();
  70. 		cc.pop_front();
  71. 		if(r>0 && arr[r-1][c]!=-1 && type_of_num(arr[r-1][c])==type)
  72. 		{
  73. 			rr.push_back(r-1);
  74. 			cc.push_back(c);
  75.  
  76. 		}
  77. 		if(c>0 && arr[r][c-1]!=-1 && type_of_num(arr[r][c-1])==type)
  78. 		{
  79. 			rr.push_back(r);
  80. 			cc.push_back(c-1);
  81.  
  82. 		}
  83. 		if(r<row-1 && arr[r+1][c]!=-1 && type_of_num(arr[r+1][c])==type)
  84. 		{
  85. 			rr.push_back(r+1);
  86. 			cc.push_back(c);
  87.  
  88. 		}
  89. 		if(c<row-1 && arr[r][c+1]!=-1 && type_of_num(arr[r][c+1])==type)
  90. 		{
  91. 			rr.push_back(r);
  92. 			cc.push_back(c+1);
  93.  
  94. 		}
  95. 	}
  96. }
  97. int main()
  98. {
  99. 	long long test;
  100. 	long long result;
  101. 	sieve();
  102. 	find_cost();
  103. 	scanf("%lld",&test);
  104. 	while(test--)
  105. 	{
  106. 		result=0;
  107. 		scanf("%lld",&row);
  108. 		for(long long i=0;i<row;i++)
  109. 			for(long long j=0;j<row;j++)
  110. 				scanf("%lld",&arr[i][j]);
  111. 		for(long long i=0;i<row;i++)
  112. 		{
  113. 			//printf("\n");
  114. 			for(long long j=0;j<row;j++)
  115. 			{
  116. 				//printf("%8lld  ",cost[arr[i][j]]);
  117. 				if(arr[i][j]!=-1)		//-1 indicates already visited
  118. 				{
  119.  
  120. 					result+=cost[arr[i][j]];
  121. 					if(type_of_num(arr[i][j])!=1)	//i.e. not prime
  122. 						bfs(i,j);
  123. 					else
  124. 						arr[i][j]=-1;
  125. 				}
  126. 			}
  127. 		}
  128. 		printf("%lld\n",result);
  129. 	}
  130. 	return 0;
  131. }
Success #stdin #stdout 0.57s 160576KB
comments (?)
stdin
copy 
1
1
3
stdout
copy 
1
https://ideone.com/xYVgC2
language:
C++ (gcc 8.3)
created:
9 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!