fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int pr[10000002];
  4. void prime()
  5. {
  6. 	for(int i=2;i<10000002;i++)
  7. 		pr[i]=1;
  8.  
  9. 	for(int i=2;i*i<10000002;i++)
  10. 	{
  11. 		if(pr[i]==1)
  12. 		{
  13. 			for(int j=2*i;j<10000002;j+=i)
  14. 			{
  15. 				pr[j]=0;
  16. 			}
  17. 		}	
  18. 	}
  19. }
  20.  
  21. int main()
  22. {
  23. 	prime();
  24. 	int n,x,y,p,q,t,f;
  25. 	int a[100005],dp[100005];
  26. 	dp[0]=0;
  27. 	cin>>n;
  28. 	for(int i=1;i<=n;i++)
  29. 	{
  30. 		cin>>a[i];
  31. 	}
  32. 	for(int i=1;i<=n;i++)
  33. 	{
  34. 	    dp[i]=dp[i-1]+pr[a[i]];
  35. 	}
  36.  
  37. 	cin>>t;
  38. 	while(t--)
  39. 	{
  40. 		cin>>f;
  41. 		switch(f)
  42. 		{
  43. 			case 0: cin>>x>>y;
  44. 			        if(pr[a[x]]!=pr[y])
  45. 			        {
  46. 			            if(pr[y]==0)
  47. 			            {
  48. 		                for(int i=x;i<=n;i++)
  49. 			                    dp[i]-=1;
  50. 			            }
  51. 			            else
  52. 			            {
  53. 			               for(int i=x;i<=n;i++)
  54. 			               {
  55. 			                    dp[i]+=1;
  56. 			               }
  57. 			            }
  58. 			        }
  59. 					a[x]=y;
  60. 				//	for(int i=1;i<=n;i++)
  61. 				//		cout<<dp[i]<<" ";
  62. 				//	cout<<endl;	
  63. 					break;
  64.  
  65. 			case 1: cin>>p>>q;
  66. 				//	cout<<dp[q]<<" "<<dp[p-1]<<endl;
  67. 					int co=dp[q]-dp[p-1];
  68. 					cout<<co<<endl;
  69. 					break;
  70. 		}
  71. 	}
  72. }
Success #stdin #stdout 0.16s 54960KB
comments (?)
stdin
copy 
5
5 12 6 9 13
5
1 2 4
0 2 7
0 4 47
1 3 5
1 1 5
stdout
copy 
0
2
4
https://ideone.com/Hcf72Q
language:
C++ (gcc 8.3)
created:
6 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!