toph - Easy Prime

Sep 29th, 2018
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2. using namespace std;
4. #define N 10000010
5. #define m 3200
6. #define pb push_back
7. typedef long long ll;
8. //const int N=1e7+2;
9. bool prime[N];
10. void primefact()
11. {
12. int i,j;
13. prime[0]=prime[1]=1;
14. for(i=4; i<=N; i+=2)
15. prime[i]=1;
16. for(i=3; i<=m; i+=2)
17. {
18. if(prime[i]==0)
19. {
20. for(j=i*i; j<=N; j+=i*2)
21. prime[j]=1;
22. }
23. }
24. }
25.
26. int main()
27. {
29. primefact();
30. int n,i,q;
31. scanf("%d",&n);
32. int ara[n+1],res[n+3];
33. res[0]=0;
34. for(i=0; i<n; i++)
35. {
36. scanf("%d",&ara[i]);
37.
38. if(prime[ara[i]]==0)
39. res[i+1]=res[i]+1;
40. else
41. res[i+1]=res[i];
42. //cout<<res[i+1]<<" ";
43.
44. }
45. // cout<<endl;
46. scanf("%d",&q);
47. while(q--)
48. {
49. int x,y,z;
50. scanf("%d %d %d",&x,&y,&z);
51. if(x==1)
52. {
53.
54. printf("%d\n",res[z]-res[y-1]);
55.
56. }
57. else
58. {
59. int temp=ara[y-1];
60. ara[y-1]=z;
61. if(temp==z)continue;
62. else if(prime[temp]==0)
63. {
64. if(prime[z]==1)
65. {
66. for(i=y; i<=n; i++)
67. {
68. res[i]-=1;
69. //cout<<res[i]<<" ";
70. }
71. //cout<<endl;
72. }
73. }
74. else if(prime[z]==0)
75. {
76. if(prime[temp]==1)
77. {
78. for(i=y; i<=n; i++)
79. {
80. res[i]+=1;
81. //cout<<res[i]<<" ";
82. }
83. // cout<<endl;
84. }
85. }
86. }
87. }
88. return 0;
89. }
RAW Paste Data