fork download
copy 
  1. #include<stdio.h>
  2.  
  3. int SG[1000];	//table to contain sprague grundy values for each starting number
  4. int F[1000],prime[1000];
  5.  
  6.  
  7. void sieve()
  8. {
  9. int i,j,count=1;
  10.  
  11. prime[0]=1;
  12. for(i=2;i<1000;i++)
  13. {
  14. if(F[i]==0)
  15. {
  16. prime[count++]=i;
  17. for(j=i+i;j<1000;j+=i)
  18. F[j]=1;
  19. }
  20. }
  21.  
  22.  
  23. }
  24.  
  25.  
  26.  
  27. int main()
  28. {
  29. // a brute force solution for the subtraction game 
  30. //Problem Statement : Remove any prime (or 1) less than N from N recursively until 1 is reached.
  31.  
  32. //Using sprague grundy theorem to label N or P positions to every game state.
  33. //P=1 winning state for the player that moved previously
  34. //N=0 winning move for the current player
  35.  
  36. SG[1]=1;	//losing state for current player(terminal position)
  37.  
  38. sieve();
  39.  
  40. int i,j,flag;
  41.  
  42. for(i=2;i<100;i++)
  43. {
  44. j=0;
  45. flag=0;
  46. while(prime[j]<i)	//prime number can be subtracted
  47. {
  48. if(SG[i-prime[j]]==1)	// next player can be given a losing position(terminal)
  49. {
  50. SG[i]=0;	//N position as a losing position can be given from current move
  51. printf("From %d move to %d\n",i,i-prime[j]);
  52. flag=1;
  53. break;
  54. }
  55. j++;
  56. }
  57.  
  58. if(flag==0)
  59. SG[i]=1;	//No terminal positions possible from this position => P position
  60.  
  61. }
  62.  
  63.  
  64. for(i=1;i<100;i++)
  65. printf("%d ",SG[i]);
  66. printf("\n\n");
  67.  
  68. return 0;
  69. }
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
Success #stdin #stdout 0s 2304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
From 2 move to 1
From 3 move to 1
From 4 move to 1
From 6 move to 5
From 7 move to 5
From 8 move to 5
From 10 move to 9
From 11 move to 9
From 12 move to 9
From 14 move to 13
From 15 move to 13
From 16 move to 13
From 18 move to 17
From 19 move to 17
From 20 move to 17
From 22 move to 21
From 23 move to 21
From 24 move to 21
From 26 move to 25
From 27 move to 25
From 28 move to 25
From 30 move to 29
From 31 move to 29
From 32 move to 29
From 34 move to 33
From 35 move to 33
From 36 move to 33
From 38 move to 37
From 39 move to 37
From 40 move to 37
From 42 move to 41
From 43 move to 41
From 44 move to 41
From 46 move to 45
From 47 move to 45
From 48 move to 45
From 50 move to 49
From 51 move to 49
From 52 move to 49
From 54 move to 53
From 55 move to 53
From 56 move to 53
From 58 move to 57
From 59 move to 57
From 60 move to 57
From 62 move to 61
From 63 move to 61
From 64 move to 61
From 66 move to 65
From 67 move to 65
From 68 move to 65
From 70 move to 69
From 71 move to 69
From 72 move to 69
From 74 move to 73
From 75 move to 73
From 76 move to 73
From 78 move to 77
From 79 move to 77
From 80 move to 77
From 82 move to 81
From 83 move to 81
From 84 move to 81
From 86 move to 85
From 87 move to 85
From 88 move to 85
From 90 move to 89
From 91 move to 89
From 92 move to 89
From 94 move to 93
From 95 move to 93
From 96 move to 93
From 98 move to 97
From 99 move to 97
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0
https://ideone.com/fHC7w8
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!