fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std ;
  4. using ll = long long ;
  5. const int MAX = 1e6 + 5 ;
  6.  
  7. bool iscomposite[MAX] ;
  8.  
  9. void preprocess(){
  10.  
  11. 	// Sieve
  12. 	iscomposite[1] = 1 ;
  13. 	for(ll i = 2 ; i < MAX ; i++)
  14. 		for(ll j = i*i ; j < MAX ; j += i)
  15. 			iscomposite[j] = 1 ;
  16.  
  17. }
  18.  
  19. void solve(){
  20.  
  21. 	int a, b ; cin >> a >> b ;
  22.  
  23. 	int cnt = 0 ;
  24. 	if(!iscomposite[a]) cnt++ ;
  25. 	if(!iscomposite[b]) cnt++ ;
  26.  
  27. 	for(int i = 0 ; i < 18 ; i++){
  28. 		int c = a + b ;
  29.  
  30. 		if(!iscomposite[c])
  31. 			cnt++ ;
  32.  
  33. 		int temp = c ;
  34. 		a = b ;
  35. 		b = c ;
  36. 	}
  37.  
  38. 	cout << cnt << "\n" ;
  39.  
  40. }
  41.  
  42. int main(){
  43.  
  44.  
  45. 	ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
  46.  
  47. 	preprocess() ;
  48.  
  49. 	int t ; cin >> t ;
  50.  
  51. 	while(t--)  solve() ;
  52.  
  53. 	return 0 ;
  54.  
  55. }
Success #stdin #stdout 0s 16208KB
comments (?)
stdin
copy 
1
100 37
stdout
copy 
4
https://ideone.com/YPMAjf
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!